LeetCode: Reverse Words in a String

LeetCode Reverse Words in a String Problem Description:

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Clarification:

  • What constitutes a word?
    A sequence of non-space characters constitutes a word.
  • Could the input string contain leading or trailing spaces?
    Yes. However, your reversed string should not contain leading or trailing spaces.
  • How about multiple spaces between two words?
    Reduce them to a single space in the reversed string.

LeetCode Reverse Words in a String Solution and Precautions:

My first initial solution would take O(N) time and O(N) space which is quite straightforward to simulate the process and find each separate word and put it into std::vector, we can get the final desired string by appending the word one by one from the tail of the word vector.  (Note: we don’t have to use std::reverse to get the desired result)

class Solution {
public:
    void reverseWords(std::string &s) {
        std::vector vecTokens;

        int i = 0, j = (int)s.size() - 1;
        while(i < = j && ' ' == s[i]) ++i;
        while(i <= j && ' ' == s[j]) --j;
        if(i > j) {
            s.clear();
            return ;
        }

        int iLastStartIndex = i;
        while(i < = j) {
            iLastStartIndex = i;
            while(i <= j && ' ' != s[++i]) ;
            vecTokens.push_back(s.substr(iLastStartIndex, i - iLastStartIndex));
            while(i <= j && ' ' == s[i]) ++i;
        }
        s.clear();
        int iSize = vecTokens.size();
        for(int idx = iSize - 1; idx >= 0; --idx) {
            s += vecTokens[idx];
            if(idx > 0)
                s.push_back(' ');
        }
    }
};

A more concise code is listed as follows which comes from the LeetCode discussion:

void reverseWords(string &s)
{
    string rs;
    for (int i = s.length()-1; i >= 0; )
    {
        while (i >= 0 && s[i] == ' ') i--;
        if (i < 0) break;
        if (!rs.empty()) rs.push_back(' ');
        string t;
        while (i >= 0 && s[i] != ' ') t.push_back(s[i--]);
        reverse(t.begin(), t.end());
        rs.append(t);
    }
    s = rs;
}

By comparing the above two pieces of code, we can lean a lesson and I think the second one is better than the first one in two aspects:
(1) The job of extracting each separate word could be done in a consistent way and in a recursive manner: thus we actually don’t have to remove the leading and trailing spaces at first but this could be done together in the process of extracting each word.
(2) Try to avoid temp memory (e.g., vecTokes in the first piece of code) as much as possible and this can help simplify the code.

LeetCode Reverse Words in a String Tips and Remarks:

We might want to pursue the solution of O(1) space:
(1) Suppose the string does not contain any leading or trailing spaces, and each word is separated by exactly one space character. O(1) Space solution could be achieved by 2 steps. Firstly, reverse (in-place reversion) the entire string. Secondly, one pass to reverse each word in the string.
(2) We try to remove the assumption in (1), i.e., we might have leading and trailing spaces, and the there could be multiple spaces between every two word. We can still adopt the method in (1) but the only concern left is how to remove the multiple spaces between words: By using Double Linked List. I think the only solution to achieve O(N) time and O(1) space is by choosing suitable data structure, here in this case it would be Doubly Linked List. I left the details and the readers please feel free to leave any comments here. :p

Written on May 17, 2014