VietMX Staff asked 3 years ago
Problem
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"Is it possible to do it in-place (without using additional data structures) and with the time complexity being O(n)?
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"Complexity Analysis
Reversing the entire string is easily done in O(n), and reversing each word in a string is also easy to do in O(n). O(n)+O(n) = O(n). Space complexity is O(1) as reversal done in-place.
Implementation
static char[] ReverseAllWords(char[] in_text)
{
int lindex = 0;
int rindex = in_text.Length - 1;
if (rindex > 1)
{
//reverse complete phrase
in_text = ReverseString(in_text, 0, rindex);
//reverse each word in resultant reversed phrase
for (rindex = 0; rindex <= in_text.Length; rindex++)
{
if (rindex == in_text.Length || in_text[rindex] == ' ')
{
in_text = ReverseString(in_text, lindex, rindex - 1);
lindex = rindex + 1;
}
}
}
return in_text;
}
static char[] ReverseString(char[] intext, int lindex, int rindex)
{
char tempc;
while (lindex < rindex)
{
tempc = intext[lindex];
intext[lindex++] = intext[rindex];
intext[rindex--] = tempc;
}
return intext;
}