Reverse The Ordering Of Words In a String Problem

Given a string s containing a set of words, transform it such that the words appear in the reverse order. Words in s are separated by one or more spaces.

Example One

Input: “I will do it.”

Output: “it. do will I”

Example Two

Input: ”   word1  word2 ” (Note: there are 3 spaces in the beginning, 2 spaces between the words and 1 space at the end.)

Output: ” word2  word1   ” (Note: there is 1 space in the beginning, 2 spaces between the words and 3 spaces at the end.)

Example Three

Input: “word1, word2;”

Output: “word2; word1,”

Notes

Input Parameters: Function one argument, string s.

output: Return a string with the answer.

Constraints:

● 1

● s contains only lowercase and uppercase alphabetical characters, spaces and punctuation marks “.,?!’:;-” (quotes not included).

Punctuation marks are considered a part of the word.

Usage of built-in string functions is NOT allowed.

An in-place linear solution is expected.

For languages that have immutable strings, convert the input string into a character array and work in-place on that array. Convert it back to the string before returning. Ignore the extra linear space used in that conversion, as long as you’re only using constant space after conversion to character array.

Trivia: This is a very old interview question. Google used it as one of their qualifier questions in Google CodeJam in the past, too.

Solutions

One idea for the solution is:

1) Reverse the whole string.

2) Then reverse the individual words.

For example, if the input is:

s = “Have a nice day!”

1) Then first reverse the whole string,

s = “!yad ecin a evaH”

2) Then reverse the individual words,

s = “day! nice a Have”

Time Complexity:

O(n).

The first pass over the string is obviously O(n/2) = O(n). The second pass is O(n + combined length of all words / 2) = O(n + n/2) = O(n), which makes this an O(n) algorithm.

Auxiliary Space used:

O(1).

Space Complexity:

O(n).

// -------- START --------

/*
Suppose s = "abcdefgh" and we call reverse_string(s[2], 4) then this function will reverse "cdef" 
part of "abcdefgh".  
*/
void reverse_string(char *str, int len)
{
    for(int i = 0; i < len / 2; i++)
    {
        swap(str[i], str[len - 1 - i]);
    }
}

string reverse_ordering_of_words(string s)
{
    int len = s.length();
    // Reverse whole string.
    reverse_string(&s[0], len);
    int word_beginning = 0;
    // Find word boundaries and reverse word by word.
    for(int word_end = 0; word_end < len; word_end++)
    {
        if(s[word_end] == ' ')	
        {
            reverse_string(&s[word_beginning] , word_end - word_beginning);
            word_beginning = word_end + 1;
        }
    }
    /* 
	If there is no space at the end then last word will not be reversed in the above for loop. 
	So need to reverse it. 
	Think about s = "hi". 
	Reverse the last word.
    */
    reverse_string(&s[word_beginning], len - word_beginning);
    return s;
}

// -------- END --------

‍