Problem statement: Given a string you have transform the string such that the order of words in the string is reversed.
Input: This is a string
Output: string a is This
Solution: First of all we consider the simple string reverse function.
1: void ReverseString(char str[])
2: {
3: int size = strlen(str);
4: for ( int i = 0, j = size - 1; i < j; i++, j-- )
5: {
6: swap( str[i] , str[j] );
7: }
8: }
This function would reverse the entire string irrespective of words.
Input: This is a string
Output: gnirts a si sihT
Our required output however is different. We need ‘string a is This’.
No compare the two;
Output1: gnirts a si sihT
Output2: string a is This
It is evident that we can get Ouput2 from output 1 just by reversing the individual words (Reversing something twice gives the original). Now that we know what to do, lets see how we can go about doing it.
First of all, it would be helpful to slightly modify the above function to work with start and end indexes of the string given.
1: void ReverseString(char str[], int start, int end)
2: {
3: for ( int i = start, j = end - 1; i < j; i++, j-- )
4: {
5: swap( str[i] , str[j] );
6: }
7: }
Now to reverse an entire string you will call this function with start = 0 and end = strlen(str). But how does this help our cause? Simple, we will first reverse the entire string and then pass the start and end index of each word to it making the words normal again.
Here is the code:
1: void ReverseWordOrder(char str[])
2: {
3: int size = strlen(str);
4: //Reverse the entire string
5: ReverseString(str, 0, size);
6: //Now we have: gnirts a si sihT
7:
8: //Now we will find start and end indexes of words
9: //and pass them to this function
10:
11: int i = 0;
12: int start, end;
13: while(i < size)
14: {
15: //find the first char of the word
16: while(str[i] == ' ')
17: i++;
18: start = i;
19: //look for the end of a word
20: while(str[i] != ' ' && str[i] != '\0')
21: i++;
22: end = i;
23: ReverseString(str, start, end);
24: }
25: }
This solution is has a running time of O(n) ( T(n) = 3n to be precise ). The first ReverseString takes n steps, the while loop itself is again has proportional to n steps. Internal call to ReverseString takes n steps in all (Can you tell how?).
Can it be further reduced without using extra memory? Post answers with proof please (for a bonus of course).
