Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
C++ code for this solution:
#include <algorithm> // For std::swap
void reverseWord(char *str, int len)
{
for (int start = 0, end = len - 1; start < end; ++start, --end)
{
std::swap(str[start], str[end]);
}
}
void reverseSentence(char *str, int len)
{
// Reverse each word in the sentence
for (int i = 0; i < len; ++i)
{
int j = i + 1;
// Find the end of the current word
while (j < len && str[j] != ' ')
{
++j;
}
reverseWord(&str[i], j - i);
i = j;
}
// Reverse the entire sentence
reverseWord(str, len);
}
I implemented your algorithm
import java.util.Scanner;
public class TextReverse{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
char[] text = scan.nextLine().toCharArray();
int start = 0;
for (int i = 0; i < text.length; i++) {
if (text[i] == ' ' || i == text.length - 1) {
int tempI = text[i] == ' ' ? i - 1 : i;
while (tempI > start) {
char temp = text[start];
text[start] = text[tempI];
text[tempI] = temp;
start++;
tempI--;
}
start = i + 1;
}
}
for (int i = 0; i < text.length / 2; i++) {
char temp = text[i];
text[i] = text[text.length - i - 1];
text[text.length - i - 1] = temp;
}
System.out.println(text);
}
}
String reverseSentence(String s) {
char temp;
for (int i = 0; i < s.length / 2; i ++) {
temp = s[s.length - 1 - i];
s[s.length - 1 - i] = s[i];
s[i] = temp;
}
int p1, p2;
p1 = p2 = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == ' ') {
reverseChar(s, p1, p2);
p1 = p2 = i + 1;
continue;
}
p2++;
}
return s;
}
void reverseChar(char[] c, int a, int b) {
//implement a reverse of char array at specific range here...
}
#include <algorithm> // Gives us std::swap to swap two elements in the array
void reverseWord(char *str, int len)
{
for (int start = 0, end = len - 1; start < end; ++start, --end)
{
std::swap(str[start], str[end]);
}
}
void reverseSentence(char *str, int len)
{
// Reverse each word in the sentence
for (int i = 0; i < len; ++i)
{
int j = i + 1;
// Find the end of the current word
while (j < len && str[j] != ' ')
{
++j;
}
reverseWord(&str[i], j - i);
i = j;
}
// Reverse the entire sentence
reverseWord(str, len);
}
More compact, using more STL:
#include <algorithm>
#include <string>
void reverseSentenceString(std::string &str)
{
int len = str.length();
for (int i = 0; i < len; ++i)
{
int j = i + 1;
// Find the end of the current word
while (j < len && str[j] != ' ')
{
++j;
}
std::reverse(str.begin() + i, str.begin() + j);
i = j;
}
std::reverse(str.begin(), str.end());
}
Why cannot we write the code like this, this code is in C#
public static string inPlaceReverse(string str)
{
StringBuilder blder = new StringBuilder();
string[] words = str.Split(new char[] { ' ' });
for (int i = words.Length-1; i >= 0; i--)
{
blder.Append(words[i]);
if(i != 0)
blder.Append(" ");
}
return blder.ToString();
}
By splitting the sentence into an array of strings, you're allocating some amount of memory that is dependent on the length of the string, so it's using O(n) space, rather than O(1). Also, I'm not extremely familiar with C#, so I'm not positive, but I assume StringBuilder is duplicating the memory as well.
Reverse sentence and then each word in the sentence
import java.util.Scanner;
class InPlaceReverse {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.println("Enter the string: ");
String sentence = s.nextLine();
sentence = reverseSentence(sentence);
System.out.println("Reversed string = " + sentence);
}
public static String reverseSentence(String sentence) {
char [] array = sentence.toCharArray();
reverse(array, 0, sentence.length() - 1);
int lastIndex = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == ' ') {
reverse(array, lastIndex, i - 1);
lastIndex = i + 1;
}
}
return new String(array);
}
public static void reverse(char[] str, int start, int end) {
while (end > start) {
char charStart = str[start];
str[start] = str[end];
str[end] = charStart;
end--;
start++;
}
}
}
#include <stdio.h>
void inplace_reverse(char* arr, int length) {
int i=0;
int j=length-2;
//printf(" original : %s ",arr);
for(;i<j;)
{
char temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
i++;
j--;
}
int k =0;
int whiteSpacePos=0;
int curr=0;
while(arr[k] != '\0')
{
if(arr[k] == ' ')
{
whiteSpacePos = k-1;
while(curr < whiteSpacePos)
{
char temp = arr[whiteSpacePos];
arr[whiteSpacePos] = arr[curr];
arr[curr] = temp;
curr++;
whiteSpacePos--;
}
curr = k+1;
}
k++;
}
printf(" reversed : %s ",arr);
}
int main(void) {
// your code goes here
char s[]= "I wish you a merry Christmas"; //"Christmas merry a you wish I"
char *p = &s;
int length = sizeof(s)/sizeof(s[0]);
printf("length: %d ",length);
inplace_reverse(s,length);
return 0;
}
By shifting the last char to first char , we can solve this problem.
public static void main(String[] args) {
String s ="I wish you a merry Christmas";
char[] f= s.toCharArray();
int k=0;
char b;
int l=0;
for(int i=0;i<s.length()-1 ;i++)
{
int j = s.length()-1;
b=f[j];
if(b==' ')
l=i;
while( j>l)
{
f[j]=f[j-1];
j--;
}
f[l]=b;
if(b==' ')
{
l++;
}
}
for(int i=0;i<f.length;i++)
{
System.out.print(f[i]);
}
}
}
public static void inplace_reverse(String s,int l){
if(l<= 1 || s.trim().indexOf(" ")<=0){
System.out.print(s);
return;
}else{
int i =0,j=l-1;
while(s.charAt(i) != ' ' && i<s.length()-1)
i++;
while(s.charAt(j) != ' ' && j>=0)
j--;
System.out.print(s.substring(j+1,l)+" ");
if(i<j)
reverse(s.substring(i+1,j),s.substring(i+1,j).length());
System.out.print(" "+s.substring(0,i));
}
}
#include <stdio.h>
#include <string.h>
void
swap (char *m, char *n)
{
char temp = *m;
*m = *n;
*n = temp;
}
void
reverse_word(char *pStart, char *pEnd)
{
while(pStart <= pEnd) {
swap(pStart, pEnd);
pStart++;
pEnd--;
}
}
void
inplace_reverse(char *arr, int length)
{
char *pCurr = arr;
char *pWord = arr;
while(*pCurr) {
if(*pCurr == ' ') {
reverse_word(pWord, pCurr-1);
pWord = pCurr+1;
}
pCurr++;
}
if(pWord != pCurr)
reverse_word(pWord, pCurr-1);
}
int
main(int argc, char *argv[])
{
char a[] = "I wish you a merry Christmas";
inplace_reverse(a, strlen(a));
printf("%s", a);
private static void reverseSentence(){
StringBuffer result = new StringBuffer();
try{
String sentence = "I wish you a merry christmas";
String[] arrayOfWords = sentence.split(" ");
int numberOfWords=arrayOfWords.length;
for(int i=numberOfWords-1;i>=0;i--){
result.append(arrayOfWords[i]).append(" ");
}
System.out.println(result);
}catch(Exception e){
e.printStackTrace();
}
}
C# Implementation.
Stack<string> stack = new Stack<string>();
StringBuilder str = new StringBuilder();
unsafe
{
fixed(char* ch = sentence)
{
for (int i = 0; ch[i] != '\0'; ++i )
{
if(ch[i] != ' ')
{
str.Append(ch[i]);
}
else
{
stack.Push(str.ToString());
//Add a space to the string
stack.Push(" ");
str.Clear();
}
ch[i]++;
}
stack.Push(str.ToString());
}
}
#include<string.h>
#include<conio.h>
#include<stdio.h>
int main()
{char str[40];
int i,n,m,v,l,len,g,j,f;
printf("enter the string size \n");
scanf("%d",&n);
g=n;
j=n;
f=n;
printf("enter your sentence\n");
for(i=0;i<n;i++)
{scanf("%c",&str[i]);}
printf("the inverse is\n");
while(g>0){
while(str[j]!=' ')
{j--;
g--;
if(j==0)
{
for(v=j;v<=f;v++)
{ printf("%c",str[v]);
}
break;}
}
if(j>0){
for(m=j;m<=f;m++)
{ printf("%c",str[m]);
}
f=0; j--; f=f+j; g--;
}
}
getch();
return 0;
}
|
public static String reverseWords(String sentence) {
char[] charArr = sentence.toCharArray();
// reverse the string
reverseCharArr(charArr, 0, charArr.length-1);
// reverse word that is has space in between
int reverseFrom = 0;
for (int spaceAt = 0; spaceAt < charArr.length; spaceAt++) {
if (charArr[spaceAt] == ' ') {
reverseCharArr(charArr, reverseFrom, spaceAt-1);
reverseFrom = spaceAt+1;
}
}
if (reverseFrom < charArr.length-1) {
reverseCharArr(charArr, reverseFrom, charArr.length-1);
}
return new String(charArr);
}
public static char[] reverseCharArr(char[] charArr, int from, int to) {
if (from < 0 || from >= charArr.length || to < 0 || from >= charArr.length || from >= to) return charArr;
for (int i = 0; i < (to-from+1)/2; i++) {
char temp = charArr[from+i];
charArr[from+i] = charArr[to-i];
charArr[to-i] = temp;
}
return charArr;
}
package com.interview.test.algorithm;
public class ReverseString {
public static void main(String[] args) {
String str = "Sunil Kumar Tamolis";
ReverseString reverseString = new ReverseString();
String rev = reverseString.reverse(str);
System.out.println(reverseString.reverse(str));
System.out.println(reverseWord(rev));
}
private String reverse(String str) {
char[] c = str.toCharArray();
int len = c.length;
int starts = 0;
int end = len - 1;
String s = "";
String e = "";
for (int i = 0; i < len / 2; i++) {
e = e + c[end];
s = c[starts] + s;
end--;
starts++;
}
if (len / 2 * 2 != len) {
return e + c[len / 2] + s;
}
return e + s;
}
private static String reverseWord(String str) {
char[] c = str.toCharArray();
int len = c.length;
String finalStr = "";
int j = 0;
while (j < len) {
String s = "";
while (len > j && c[j] != ' ') {
s = c[j] + s;
j++;
}
j++;
finalStr = finalStr + s + " ";
}
return finalStr;
}
}
#include <stdio.h>
#include <string.h>
void inplace_reverse( char* arr, int length);
int main()
{
char arr[] = "I wish you a merry Christmas";
inplace_reverse( arr, strlen(arr));
return 0;
}
void inplace_reverse( char* arr, int length)
{
while( --length >= 0 ) {
if( arr[length] == ' ' ) {
printf("%s ", arr+(length+1));
arr[length] = '\0';
}
}
printf("%s\n",arr);
}
The code above has been written by me. Here the catch is, you don't have to worry about changing the string as the function declaration is void, we just need to print them in reverse order. The above code doesn't use extra space other than the function parameters.
One problem: The function returns void, but you are passing a pointer into it, so if you print out the original string after you call this function, you'll find that it will only print "I". This is because you're replacing every space with a null terminator. You can test this by simply changing your main function to:
int main()
{
char arr[] = "I wish you a merry Christmas";
inplace_reverse( arr, strlen(arr));
printf("After function call: %s\n", arr); // Note this added print statement
return 0;
}
Your output looks like this:
Christmas merry a you wish I
After function call: I
Side note: The question asks for the sentence to be reversed in place, which means you are to modify the original array so that it contains the reversed sentence.
Algo:
Step 1 - Store each character in a Stack
Step 2 - Now move the pointer from the top of stack to the location where either the first space is encountered or you reach the end of stack. Starting from the location next to this, keep removing the characters till you reach the top of stack; remove a space (if any).
Step3 - repeat Step 2 till end of stack is reached.
The runtime complexity is O(2N) which is O(N)
The space complexity is O(1)
/** Created by yeison on 1/19/2015. */
public class ReverseInPlace {
public static void main(String[] args){
char[] s1 = "I am floating in a tin can.".toCharArray();
// The result will be "can. tin a in floating am I"
reverseSentence(s1);
System.out.println(s1);
}
/** Reverses the order of the words in a sentence in place
* so that a sentence such as: "This is an example" will end up
* as "example an is This" . */
public static void reverseSentence(char[] sentence){
// First reverse the whole string
reverseString(sentence, 0, sentence.length);
// Then reverse each word
for (int i = 0, start = 0; i < sentence.length; i++) {
if(sentence[i] == ' '){
reverseString(sentence, start, i);
start = i+1;
}
}
}
public static void reverseString(char[] string, int start, int end){
for (int i = start, j = end-1; i < start + (end-start)/2; i++, j--) {
swap(string, i,j);
}
}
private static void swap(char[] string, int i, int j) {
char temp = string[i];
string[i] = string[j];
string[j] = temp;
}
}
Here's a solution using JavaScript. Please note, Strings aren't mutable in JavaScript. Therefore, we need to convert a string into an Array of Characters. Let's assume this happens independent of our algorithm.
// Preparation
var sentence = 'welcome to the jungle'.split('');
// Algorithm
reverseSentenceArray(sentence);
console.log(sentence.join(''));
function reverseCharactersInArray(a, start, end) {
var c;
while (start < end) {
c = a[start];
a[start] = a[end];
a[end] = c;
start++;
end--;
}
return a;
}
function reverseWordsInArray(a, start, end) {
var startOfWord = 0;
var endOfWordProbe = 1;
while (endOfWordProbe <= end) {
if (a[endOfWordProbe] === ' ') {
reverseCharactersInArray(a, startOfWord, endOfWordProbe - 1);
startOfWord = endOfWordProbe + 1;
} else if (endOfWordProbe === end) {
reverseCharactersInArray(a, startOfWord, end);
}
endOfWordProbe++;
}
}
function reverseSentenceArray(a) {
reverseCharactersInArray(a, 0, a.length - 1);
reverseWordsInArray(a, 0, a.length - 1);
}
def inplace_reverse(string, length)
revert_word(string, 0 , length-1)
i = 0
while i < length
j = i
while (string[i] != " " and i < length) do
puts i
i += 1
end
puts string[j..i-1]
revert_word(string, j, i-1)
puts "#{j} #{i-1} "
i += 1
end
puts string
end
#memory keep 1
def revert_word(word, start, last)
puts word
j = 0
(start..((last + start)/2)).each do |i|
word[i], word[last-j] = word[last-j], word[i]
j += 1
end
end
a = "I wish you a merry Christmas"
inplace_reverse(a, a.size)
Logic is simple. First reverse the sentence then reverse the words
void str_reverse(char* arr, int start, int end) {
for (;start < end; start++, end--) {
char temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
}
void inplace_reverse(char* arr, int length) {
if (arr == NULL)
return;
if (length <= 0)
return;
str_reverse (arr, 0, length - 1);
int start = 0;
int next = start;
for(; next < length; ) {
while(next < length && arr[next] != ' ') next++;
str_reverse(arr, start, next - 1);
start = next + 1;
next = start;
}
}
import javax.sound.sampled.ReverbType;
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.print(revers("I wish you a merry Christmas"));
}
public static String revers(String ch)
{
String reversedString="";
String word="";
int position;
while(!ch.equals(""))
{
position = ch.indexOf(" ");
if(position>0)
{
word = ch.substring(0,position);
reversedString = word +" "+reversedString;
ch = ch.substring(position+1, ch.length());
}
else
{
reversedString = ch + " "+ reversedString;
ch = "";
}
}
return reversedString.substring(0,reversedString.length()-1);
}
}
Here is my code. Of course it will not work if I have two white space or more.
void reverse(char* str, int start, int stop)
{
int len = stop - start + 1;
for(int i = 0, i < len/2 + start; ++i)
{
char temp = str[i+start];
str[i+start] = str[stop-i];
str[i+stop] = temp;
}
}
void reverseSentence(char* str, int size)
{
reverse(str, 0, size-1);
int start = 0;
int stop = 0; // doesn't matter actually
for(int i=0; i<size; ++i){
if(str[i] == ' '){
stop = i-1;
reverse(str, start, stop);
start = i+1;
}
}
reverse(str, start, size-1);
}
I struggled with this until I was advised of the trick of two-step, reverse entire sentence, reverse each word. Then it's easy
Complexity O(2.n)
Space O(1)
Ruby code, but C with C-str would be very similar
def reverse(s)
def swap(s, l, r)
for i in 0..(r - l) / 2
s[l + i], s[r - i] = s[r - i], s[l + i]
end
s
end
s = swap(s, 0, s.length - 1)
l = 0
r = 0
loop do
loop do
break if r >= s.length - 1 || s[r] == " "
r += 1
end
s = swap(s, l, r - 1)
l = r + 1
r = l
break if r >= s.length - 1
end
s
end
puts reverse("i wish you a merry christmas")
package _Bsm;
public class InplaceReverse {
public static void inplaceReverse(char [] str, int n) {
if (n <= 1) return;
int s = 0, e = n -1;
reverse(str, s, e);
s = 0;
for (int i = 0; i < str.length; i++) {
if(i == n-1) {
reverse(str, s, i);
}
if(str[i] == ' ') {
reverse(str, s, i-1);
s = i + 1;
}
}
}
private static void reverse(char[] str, int s, int e) {
while ( s <= e){
swap(str, s, e);
s++; e--;
}
}
private static void swap(char[] str, int s, int e) {
char temp = str[s];
str[s] = str[e];
str[e] = temp;
}
}
package _Bsm;
public class InplaceReverse {
public static void inplaceReverse(char [] str, int n) {
if (n <= 1) return;
int s = 0, e = n -1;
reverse(str, s, e);
s = 0;
for (int i = 0; i < str.length; i++) {
if(i == n-1) {
reverse(str, s, i);
}
if(str[i] == ' ') {
reverse(str, s, i-1);
s = i + 1;
}
}
}
private static void reverse(char[] str, int s, int e) {
while ( s <= e){
swap(str, s, e);
s++; e--;
}
}
private static void swap(char[] str, int s, int e) {
char temp = str[s];
str[s] = str[e];
str[e] = temp;
}
}
package _Bsm;
public class InplaceReverse {
public static void inplaceReverse(char [] str, int n) {
if (n <= 1) return;
int s = 0, e = n -1;
reverse(str, s, e);
s = 0;
for (int i = 0; i < str.length; i++) {
if(i == n-1) {
reverse(str, s, i);
}
if(str[i] == ' ') {
reverse(str, s, i-1);
s = i + 1;
}
}
}
private static void reverse(char[] str, int s, int e) {
while ( s <= e){
swap(str, s, e);
s++; e--;
}
}
private static void swap(char[] str, int s, int e) {
char temp = str[s];
str[s] = str[e];
str[e] = temp;
}
}
public class ReverseSentence {
public static void main(String[] args) {
char input[] = "I wish you a merry Christmas".toCharArray();
recursive(input, input.length, input.length);
}
private static int recursive(char input[], int index, int indexMax) {
--index;
if (index < 0) {
return -1;
}
int minIndex = -1;
if (input[index] == ' ') {
return index;
}
minIndex = recursive(input, index, indexMax);
System.out.print(input[index]);
if (index + 1 == indexMax) {
System.out.print(' ');
recursive(input, minIndex, minIndex);
}
return minIndex;
}
}
public class ReverseSentence {
public static void main(String[] args) {
char input[] = "I wish you a merry Christmas".toCharArray();
recursive(input, input.length, input.length);
}
private static int recursive(char input[], int index, int indexMax) {
--index;
if (index < 0) {
return -1;
}
int minIndex = -1;
if (input[index] == ' ') {
return index;
}
minIndex = recursive(input, index, indexMax);
System.out.print(input[index]);
if (index + 1 == indexMax) {
System.out.print(' ');
recursive(input, minIndex, minIndex);
}
return minIndex;
}
}
public class ReverseSentence {
public static void main(String[] args) {
char input[] = "I wish you a merry Christmas".toCharArray();
recursive(input, input.length, input.length);
}
private static int recursive(char input[], int index, int indexMax) {
--index;
if (index < 0) {
return -1;
}
int minIndex = -1;
if (input[index] == ' ') {
return index;
}
minIndex = recursive(input, index, indexMax);
System.out.print(input[index]);
if (index + 1 == indexMax) {
System.out.print(' ');
recursive(input, minIndex, minIndex);
}
return minIndex;
}
}
public class ReverseSentence {
public static void main(String[] args) {
char input[] = "I wish you a merry Christmas".toCharArray();
recursive(input, input.length, input.length);
}
private static int recursive(char input[], int index, int indexMax) {
--index;
if (index < 0) {
return -1;
}
int minIndex = -1;
if (input[index] == ' ') {
return index;
}
minIndex = recursive(input, index, indexMax);
System.out.print(input[index]);
if (index + 1 == indexMax) {
System.out.print(' ');
recursive(input, minIndex, minIndex);
}
return minIndex;
}
}
public class ReverseSentence {
public static void main(String[] args) {
char input[] = "I wish you a merry Christmas".toCharArray();
recursive(input, input.length, input.length);
}
private static int recursive(char input[], int index, int indexMax) {
--index;
if (index < 0) {
return -1;
}
int minIndex = -1;
if (input[index] == ' ') {
return index;
}
minIndex = recursive(input, index, indexMax);
System.out.print(input[index]);
if (index + 1 == indexMax) {
System.out.print(' ');
recursive(input, minIndex, minIndex);
}
return minIndex;
}
}
public class ReverseSentence {
public static void main(String[] args) {
char input[] = "I wish you a merry Christmas".toCharArray();
recursive(input, input.length, input.length);
}
private static int recursive(char input[], int index, int indexMax) {
--index;
if (index < 0) {
return -1;
}
int minIndex = -1;
if (input[index] == ' ') {
return index;
}
minIndex = recursive(input, index, indexMax);
System.out.print(input[index]);
if (index + 1 == indexMax) {
System.out.print(' ');
recursive(input, minIndex, minIndex);
}
return minIndex;
}
}
public class ReverseSentence {
public static void main(String[] args) {
char input[] = "I wish you a merry Christmas".toCharArray();
recursive(input, input.length, input.length);
}
private static int recursive(char input[], int index, int indexMax) {
--index;
if (index < 0) {
return -1;
}
int minIndex = -1;
if (input[index] == ' ') {
return index;
}
minIndex = recursive(input, index, indexMax);
System.out.print(input[index]);
if (index + 1 == indexMax) {
System.out.print(' ');
recursive(input, minIndex, minIndex);
}
return minIndex;
}
}
public class StringReplace {
public String[] sentenceReverse(String[] str)
{
int len = str.length;
char[] word;
for(int j=0, k=len-1; j<=k; j++,k--)
{
str[j]=wordReverse(str[j].toCharArray());
str[k]=wordReverse(str[k].toCharArray());
String temp = str[k];
str[k]= str[j];
str[j]=temp;
}
return str;
}
public String wordReverse (char[] charArr)
{
String word = null;
int wordLen = charArr.length;
for(int j=0, k=wordLen-1; j<=k; j++,k--)
{
char temp = charArr[k];
charArr[k]= charArr[j];
charArr[j]=temp;
}
word = new String(charArr);
return word;
}
public static void main(String args[])
{
StringReplace sr = new StringReplace();
String str = "I hope this just works fine very first time itself";
String[] sArr = str.split(" ");
String[] newArr = sr.sentenceReverse(sArr);
String newSentence = "";
for(int i=0; i<newArr.length; i++)
{
newSentence = newSentence.concat(newArr[i]+" ");
}
System.out.println("The reversed string is : "+newSentence);
}
}
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
string inplace_reverse(string s)
{
reverse(s.begin(), s.end());
enum State {IN,OUT};
State state = OUT;
int start, end;
for(int i=0; i<s.size(); i++)
{
if(s[i] == ' ' && state == IN)
{
reverse(s.begin()+start,s.begin()+i);
state = OUT;
}
else if(s[i] != ' ' && state == OUT)
{
start = i;
state = IN;
}
}
if(state == IN)
{
reverse(s.begin()+start,s.end());
}
return s;
}
int main()
{
string sentence = "I wish you a merry christmas";
cout << "reverse_sentence.cppp\n";
cout << inplace_reverse(sentence);
return 0;
}
function inPlaceReverse(str) {
function reverse(str, i, j) {
j--;
while (i < j) {
tmp = str[i];
str[i] = str[j];
str[j] = tmp;
i++;
j--;
}
}
str = str.split('');
var tmp, i = 0, j = str.length;
//Completely reverse string first
reverse(str, i, j);
i = 0, j = 0;
//The reverse words
while (i < str.length) {
while (/\w/.test(str[j]) === true && j < str.length) {
j++;
};
reverse(str, i, j);
j++;
i = j;
}
return str.join('');
}
Simple recursive solution in Python. :-)
def rev_in_place(str):
try:
first = str.index(" ")
last = str.rindex(" ")
except:
# no space
return str
if (first == last):
return str
return str[last + 1:] + str[first] + rev_in_place(str[first+1:last]) + str[last] + str[:first]
print(rev_in_place('I wish you a merry Christmas'))
Simple O(n) solution in Python.
def rev_in_place(str):
try:
first = str.index(" ")
last = str.rindex(" ")
except:
# no space
return str
if (first == last):
return str
return str[last + 1:] + str[first] + rev_in_place(str[first+1:last]) + str[last] + str[:first]
print(rev_in_place('I wish you a merry Christmas'))
Simple solution in Python :-)
def rev_in_place(str):
try:
first = str.index(" ")
last = str.rindex(" ")
except:
# no space
return str
if (first == last):
return str
return str[last + 1:] + str[first] + rev_in_place(str[first+1:last]) + str[last] + str[:first]
print(rev_in_place('I wish you a merry Christmas'))
Simple algorithmic trick for this problem.
public static void ReverseWords(char[] A)
{
Reverse(A, 0, A.Length);
int start = 0;
for(int i = 0; i < A.Length; i++)
{
if(A[i] == ' ')
{
Reverse(A, start, i);
start = i+1;
}
}
Reverse(A, start, A.Length);
}
private static Reverse(char[] A, int start, int end)
{
for(int i = start; i < end/2; i++)
{
char swap = A[i];
A[i] = A[end-i];
A[end-i] = swap;
}
}
Simple algorithmic trick for this problem.
public static void ReverseWords(char[] A)
{
Reverse(A, 0, A.Length);
int start = 0;
for(int i = 0; i < A.Length; i++)
{
if(A[i] == ' ')
{
Reverse(A, start, i);
start = i+1;
}
}
Reverse(A, start, A.Length);
}
private static Reverse(char[] A, int start, int end)
{
for(int i = start; i < (start+end)/2; i++)
{
char swap = A[i];
A[i] = A[end-i];
A[end-i] = swap;
}
}
/*
Reverse the words (space delimited tokens, anyway) in a sentence.
Usage: ./a.out 'Put the sentence between two single quotes.'
Reverse string with converging pointers, "unreverse" words when you have
finished the token. When pointers converge, start at least word pointer
and unreverse the words in the second half. All that unreversing seems
kind of silly: I'd like to see another way.
Note: I'm not a big believer in XOR swaps. It's a macro. Feel free.
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define SWAP(s,i,j,temp) temp=s[i]; s[i] = s[j]; s[j]=temp;
main(int argc, char **argv) {
int i,j,k,w,len;
register char *s;
register char temp = 0x00;
if (argc > 0) {
s=calloc(strlen(argv[1]+4 % 4),1);
if (!s) {
printf("calloc() failed.\n");
exit(1);
}
strncpy(s,argv[1],strlen(argv[1]));
} else {
printf("Nothing to do.\n");
exit(0);
}
w = 0;
i = 0;
len = strlen(s);
j = len-1;
printf("sentence: %s\n",s);
do {
SWAP(s,i,j,temp);
if (s[i] == ' ') {
k = i-1;
do {
SWAP(s,w,k,temp);
} while (--k > w++);
w = i+1;
}
} while(--j > i++);
for (i=w; i<len+1; i++) {
if (s[i] == ' ' || i == len) {
k = i-1;
do {
SWAP(s,w,k,temp);
} while (--k > w++);
w = i+1;
}
}
printf("reversed: %s\n",s);
exit(0);
}
package hello;
public class ReverseSring {
public static void main(String[] args) {
StringBuilder s = new StringBuilder("I wish you a merry Christmas") ;
for(int i =0; i<s.length() ; i ++){
char temp = s.charAt(i);
s.setCharAt(i, s.charAt(s.length()- i - 1));
s.setCharAt(s.length()- i - 1, temp);
if(i == (s.length()- i - 1) || (i+1) == (s.length()- i - 1)){
break;
}
}
int startIndex= 0;
int endIndex = 0;
for(int i =0 ; i<s.length() ; i++){
//int startIndex = 0;
//int endIndex = 0;
if(s.charAt(i) == ' ' || i == s.length() - 1 ){
if(i == s.length()-1){
endIndex = i;
}else{
endIndex = i-1;
}
int count = 0;
for(int j =startIndex; j<endIndex+1 ; j ++){
char temp = s.charAt(j);
int length = endIndex - startIndex + 1;
s.setCharAt(j, s.charAt(endIndex- count ));
s.setCharAt(endIndex- count , temp);
if(j == endIndex- count || (j+1) == (endIndex- count)){
break;
}
count++;
}
startIndex = i+1;
}
}
System.out.println(s);
}
}
Here is C++ version of Solution running in O(N), where N is the length of the sentence.
It first reverse the sentence and reverse the words.
#include<iostream>
#include<climits>
#include<string>
#include<cstdlib>
using namespace std;
void reverse(char* arr, int start, int end)
{
int s = start, e = end;
char temp;
while(s < e)
{
temp = arr[s];
arr[s] = arr[e];
arr[e] = temp;
s++;
e--;
}
}
void reverse_sentence(char *arr, int len)
{
reverse(arr, 0, len-1);
cout << arr <<endl;
int s = INT_MIN, e;
for(int i = 0; i < len; i++)
{
if (arr[i] == ' ')
{
if (s == INT_MIN)
{
cout <<"[ERROR] whitespace before the sentence"<<endl;
return;
}
e = i -1;
reverse(arr, s, e);
s = INT_MIN;
}else {
if (s == INT_MIN)
s = i;
if (i == len-1 && s != INT_MIN)
{
reverse(arr, s, i);
}
}
}
}
void reverse(char *arr, int length)
{
for (int index = 0; index < length/2; index++)
{
char tmp = arr[index];
arr[index] = arr[length-index-1];
arr[length-index-1] = tmp;
}
}
void inplace_reverse(char* arr, int length)
{
reverse(arr,length);
int startIndex = 0;
for (int index = 0; index < length; index++)
{
if (arr[index] == ' ')
{
reverse(arr+startIndex,index-startIndex);
startIndex = index+1;
}
}
reverse(arr,index-startIndex);
}
void reverseSentence(String s) {
ArrayList<String> list = new ArrayList<>();
String word = "";
for(int i = 0; i < s.length(); i++) {
if (s.charAt(i) != ' ') {
word += s.charAt(i);
} else {
list.add(word);
word = "";
}
if (i == s.length() - 1) list.add(word);
}
word = "";
for(int i = list.size() - 1; i >= 0; i--) {
word += list.get(i);
if (i > 0) word += " ";
}
System.out.println(word);
}
public String reverse (String str)
{
String newStr ="";
String rev[] = str.split(" ");
int words = rev.length;
for(int i=words-1; i>0;i--)
{
newStr+= rev[i]+" " ;
}
return newStr;
}
Algo: Time O(n) and space O(1)
- xyz January 17, 20151 . Reverse each word in sentence
2 . Reverse sentence it self
3 . Return sentence
e.g.
I wish you a merry Christmas
step 1 . I hisw uoy a yrrem samtsirhC
step 2 . Christmas merry a you wish I
Method 2:
1. Token the string on space (' ') using strtok() in c++
2. Reverse the all tokens get the answer
O(n) in time and O(n) in space if we store token separately .
else O(n) time and O(1) in space
In python just one line
print ' '.join(s.split()[::-1])