Problem

More LeetCode Discussions
Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

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

Could you do it in-place without allocating extra space?

Solution

先reverse string，之后reverse每一个word。

class Solution {
public:
    void reverseStr(string &s, int i, int j) {
        while (i < j) {
            char c = s[i];
            s[i] = s[j];
            s[j] = c;
            i++;
            j--;
        }    
    }
    
    void reverseWords(string &s) {
        if (s.size() == 0) {
            return;
        }
        
        reverseStr(s, 0, s.size() - 1);
        
        int start = 0;
        int end;
        for(int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                end = i - 1;
                reverseStr(s, start, end);
                start = i + 1;
            }
        }
        
        if (s[s.size() - 1] != ' ') {
            reverseStr(s, start, s.size() - 1);
        }
    }
};