Reverse the ordering of words in a string

algorithm data-structures string
Arnkrishn picture Arnkrishn · Jun 17, 2009 · Viewed 191.9k times · Source

I have this string s1 = "My name is X Y Z" and I want to reverse the order of the words so that s1 = "Z Y X is name My".

I can do it using an additional array. I thought hard but is it possible to do it inplace (without using additional data structures) and with the time complexity being O(n)?

Answer

Bill the Lizard picture Bill the Lizard · Jun 17, 2009

Reverse the entire string, then reverse the letters of each individual word.

After the first pass the string will be

s1 = "Z Y X si eman yM"

and after the second pass it will be

s1 = "Z Y X is name My"

Related questions

Ukkonen's suffix tree algorithm in plain English

I feel a bit thick at this point. I've spent days trying to fully wrap my head around suffix tree construction, but because I don't have a mathematical background, many of the explanations elude me as they start to make …

Read More
Best data structure for implementing a dictionary?

What would be the best data structure to store all the words of a dictionary? The best I could think of was to use a HashMap, which will map to a HashTable. Basically, depending upon the first character, we will …

Read More
KMP prefix table

I am reading about KMP for string matching. It needs a preprocessing of the pattern by building a prefix table. For example for the string ababaca the prefix table is: P = [0, 0, 1, 2, 3, 0, 1] But I am not clear on what does the …

Read More