CareerCup

package com.algorithm.amazon;

import java.util.StringTokenizer;

public class ReverseSentence {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(reverseWordsInSentence("I am Don"));
	}

	private static String reverseWordsInSentence(String string) {
		// TODO Auto-generated method stub
		StringTokenizer st=new StringTokenizer(string," ");
		String revString="";
		while(st.hasMoreTokens())
		{
			revString=st.nextToken()+" "+revString;
					
		}
		return revString;
	}


}

Reverse complete string and then reverse each words from starting.
Eg: I am Don

Step 1: noD ma I
Step 2: Don am I

Please suggest me better solution if exist.

If additional buffer is allowed - stack can help.

A little python code the works. Complexity is O(n).

def f(x): return x+" "
def f(x): return x+" "

def reverse(toReverse):
answer=toReverse.split()
answer.reverse()
answer="".join(map(f,answer))
return answer

if __name__ == '__main__':
print (reverse("I am trying to learn python"))

a straight forward Java Solution:

public String reverse(String string) {
		String stAry[] = string.split(" ");
		StringBuilder b = new StringBuilder();
		for (int i = stAry.length - 1; i >= 0; i--) {
			b.append(stAry[i]).append(" ");
		}
		return b.toString().substring(0, b.lastIndexOf(" "));
	}

#include<algorithm>
#include<string>
#include<iostream>

using namespace std;

int main()
{

string inpStr,inpWrd;
int age;

cout << "Enter the string :";

getline(cin,inpStr);

cout<<"Input String is : "<<inpStr<<endl;

string delimiters = " ";
size_t current;
size_t next = -1;
do
{
  current = next + 1;
  next = inpStr.find_first_of( delimiters, current );
  inpWrd=inpStr.substr( current, next - current ) ;
  reverse(inpWrd.begin(),inpWrd.end());

  cout<<inpWrd<<" ";
}
while (next != string::npos);

cout<<endl;
return(0);
}

Complexity :
Time : O(n)

Input: I am Don
Output: Don am I

Algorithm:
- Start on the input string from the reverse side.
- If encounter any character other than space, put that in a stack.
- If encountered a space, take all the characters out of the stack one by one and add them to the output string, append the space, and continue.
- As you are traversing in reverse, you'll encounter the word letters in reverse. Pushing them in stack and popping them out will switch them to make a forward word.

Recursively

public static string ReverseStringInOrder(string x)
        {
            char[] a = x.ToCharArray();
            char[] b = new char[a.Length];
            ReverseWordInOrder(a, a.Length-1, b);
            return new string(b);
        }

        public static void ReverseWordInOrder(char[] a, int s, char[] res)
        {
            if (s < 0)
                return;

            int sp = -1;
            for (int i = s; i >= 0; i--)
            {
                if (a[i] == ' ')
                {
                    sp = i;
                    break;
                }
            }
            for (int j1 = sp+1, j2=res.Length-1-s; j1 <= s; j1++, j2++)
            {
                res[j2] = a[j1];
            }
            if (!(sp == -1))
            {
                res[a.Length - 1 - sp] = ' ';
                ReverseWordInOrder(a, sp - 1, res);
            }
            return;
       }

Iteratively

public static string ReverseStringInOrder2(string x)
        {
            char[] res = new char[x.Length];
            int s = 0;
            int sp = -1;
            for (int i = 0; i <= x.Length - 1; i++)
            {
                if (x[i] == ' ')
                {
                    sp = i;
                    for (int j1 = s, j2 = res.Length - sp; j1 < sp; j1++, j2++)
                    {
                        res[j2] = x[j1];
                    }
                    res[res.Length - 1 - sp] = ' ';
                    s = sp+1;
                    sp = -1;
                }
            }
            if (sp == -1)
            {
                for (int m1 = s, m2 = 0; m1 < x.Length; m1++, m2++)
                {
                    res[m2] = x[m1];
                }
            }
            return new string(res);
        }

Java code using a Stack:

private static String stackToString(Stack<String> stack) throws IllegalArgumentException {
		if (stack==null){throw new IllegalArgumentException("null stack");}
		StringBuilder sb = new StringBuilder();
		
		while (!stack.isEmpty()){
			sb.append(stack.pop());
			if (!stack.isEmpty()){sb.append(' ');}
		}
		return sb.toString();
	}
	
	public static String reverseSentence(String s) throws IllegalArgumentException {
		if (s==null){throw new IllegalArgumentException("null string");}
		StringBuilder sb = new StringBuilder();
		Stack<String> stack = new Stack<>();
		
		for (int i=0;i<s.length();i++){
			if (s.charAt(i)==' '){
				stack.push(sb.toString());
				sb = new StringBuilder();
			}
			else {sb.append(s.charAt(i));}
		}
		stack.push(sb.toString());
		
		return stackToString(stack);
	}

Recursively (assuming I can use some helper methods like indexOf and that space is the only tokenizer and there aren't contiguous space)

String reverse(String s) {
		int pos = s.indexOf(" ");
		if(pos < 0)
			return s;
		else return reverse(s.substring(pos+1)) + " " + s.substring(0, pos);
	}

def func(string):
s=string.split(" ")
s=" ".join(s[::-1])
return s

Why don't you just store the splitted words into a simple array and then iterate through this array until its middle part swapping 'i' element by 'i + length - i' ?

Here it is

public class ReverseSentence {

  public String get(String data) {
    if (data == null || data.length() <= 2)
      return data;

    char space = ' ';
    char[] src = data.toCharArray();
    char[] reversed = new char[data.length()];
    
    int pos = 0, end = data.length();
    
    for (int index = data.length() - 1; index >= 0; index--) {
      int start = -1;
      if (src[index] == space)
        // word starts next to space
        start = index + 1;
      else if (index == 0)
        start = 0;

      if (start != -1 && start <= end) {
        int len = end - start;
        // copy the word
        System.arraycopy(src, start, reversed, pos, len);
        end = index;
        pos += len;
        if (pos < data.length())
          // add space between words
          reversed[pos++] = space;
      }
    }
    return new String(reversed);
  }

  public static void main(String[] args) {
    ReverseSentence rs = new ReverseSentence();
    System.out.println(rs.get("repeat these words to reverse the sentence "));
  }
}

A no additional buffer solution:

Use two parsers, p1, p2;

int p1 = 0, p2 = 0
	// this function parse through str from index p2 to find the index for next space
	p2 = searchNextSpaceIndex(str, p2) - 1
	while p2 != -1{
             while p1 < p2 {
	         swap(str, p1++, p2--)
	      }
		p1 = p2
		p2 = searchNextSpaceIndex(str, p2) - 1
	 }

Complexity :
Time : O(n)
Space: O(1)