Code Kata – Reverse words in a string

Dave Thomas creates a website called Code Kata, Who encourage developers improve their skills by keep practicing coding, trying to find better solutions for some questions.

Today I met an interesting question: How to reverse words in a string?
For example, given a string "The quick brown fox jumped over the lazy dog", reversed string needs to be “dog lazy the over jumped fox brown quick The”. The thing is you can not use extra memory to do it, you had better manipulate the reverse logic in the original text string.

To solve this question, I remembered I read a good book several years ago, it is called Programming Pearls ,written by John Bentley.

In chapter 2, section “The power of Primitive”, the author gives the solution of transform an array vector, which is clean, elegant and efficient. I used this solution to solve this problem.
The algorithm has two steps:
1. First reverse the entire string by character
For example: "The quick brown fox jumped over the lazy dog" becomes
“god yzal eht revo depmuj xof nworb kciuq ehT”
2. Then reverse each word by character
For example: “god yzal eht revo depmuj xof nworb kciuq ehT” becomes
“dog lazy the over jumped fox brown quick The”

You see it is pretty easy, right? No need extra memeory, no need substring.This is the power of the algorithm.

Here I post the java version of the solution, you can easily implement this algorithm in C or other language.

public class StringRerverse {

private int wordStartIndex;
private int wordEndIndex;
private StringBuffer sBuffer;

String reverse(String string)
{

this.sBuffer = new StringBuffer(string);

sBuffer.reverse();

int size = sBuffer.length();
int pos = 0;

while(pos < size)
{
if(findNextWord(pos) == true)
{
reverseWord(sBuffer,wordStartIndex,wordEndIndex);
pos = wordEndIndex+1;
}
else
{
break;
}
}


return sBuffer.toString();

}
boolean findNextWord(int startFrom)
{
int start = startFrom;

while (start< sBuffer.length()-1 && sBuffer.charAt(start) == ' ')
{
start++;
}
if(start == sBuffer.length() -1 )
{
return false;
}

wordStartIndex = start;

int end = start+1;
while(end < sBuffer.length()-1 && sBuffer.charAt(end) != ' ' )
{
end++;
}
if(end == sBuffer.length() -1 )
{
wordEndIndex = end;
}
else
{
wordEndIndex= end-1;
}
return true;
}

void reverseWord(StringBuffer sBuffer,int wordStartIndex, int wordEndIndex)
{
int length = wordEndIndex - wordStartIndex + 1;
for(int j = 0; j<length/2; j++)
{

int startIndex = wordStartIndex + j;
int endIndex = wordEndIndex - j;
char c = sBuffer.charAt(startIndex);
sBuffer.setCharAt(startIndex, sBuffer.charAt(endIndex));
sBuffer.setCharAt(endIndex, c);
}
}



public static void main(String[] args)
{
StringRerverse reverse = new StringRerverse();

String string = new String("The quick brown fox jumped over the lazy dog");
String reverseString = reverse.reverse(string);
System.out.println("reversed String: "+reverseString);

}
}