Been a long time since I have written algorithmic code. I decided to try my hand in one of the string related puzzles.
Reverse words in a sentence, supplied as a string. For example, if the original string is “I have to be reversed.”, then the reversed string would be “reversed. be to have I” (Note that punctuations are treated in par with characters)
I have come across many algorithms which runs in linear time. But I was not satisfied with them.
- Most of them use the reverse string functionality
- For each word you find from the end of original string, if you apply the reverse string functionality then your algorithm becomes O(mn), where n-> length of the string and m-> average length of a word
- Also I was not very comfortable with the Temporary variable usage for this algorithm
So I decided to find out an algorithm which serves the following purposes:
- Eliminate Temporary variable usage
- Runs in linear time, O(n)
Following is an attempt to arrive at such an algorithm. I have provided the Java code which implements this algorithm. Please note that I am using “mutable” StringBuffer for efficient space management.
- Start with original string – ‘original’
- Find out length of the string – ‘len’
- Initialize an integer array, spaceArray whose value denotes the positions of space in the ‘original’ string
- Scan through the string from beginning to end, using ‘len’
- If current character is a space
- add the current index of string to the spaceArray
- Increment spaceArray index
- Continue loop
- Else Continue loop
- End Scan
- Create empty String – ‘reverse’
- Start a loop: index=(last value in spaceArray+1). Loop condition=(index < string length)
- Get the character from ‘original’ at position ‘index’
- This will retrieve portion of the original string starting after the last occurrence of space character
- If index equals string length (last iteration)
- Add the space character, which must be character at original string at the index, specified by current value of spaceArray
- If you have exhausted spaceArray, break out of loop
- Decrement spaceArray index value
- Modify loop indices: index=current value of spaceArray. Loop condition=(index < previous value of spaceArray).
- If (index+1) = previous value of spaceArray, then it means we have consecutive space characters in the String
- In this case, decrement index value by 1
- Continue loop
- Proceed till the end of this loop
- Since we have broken the loop at the exhaustion of spaceArray, still the first word of the original string is not added to reverse string
- Add the first word of the ‘original’ to ‘reverse’
- Finally, ‘reverse’ will have the required value
Java code for this can be found at this location:
Thus you can see that all operations are O(n). So the overall algorithm runs at O(n). Also there is no usage of temporary string for reversing. Also it handles the condition, when the string has consecutive space characters…
Any comments on this are welcome!!