博文中会简要介绍Leetcode P0186题目分析及解题思路。

“Reverse Words in a String II”这道题是p0151的衍生题。这道题和p0151不同的是前后没有空格并且中间用于分割单词的空格每次之后出现一个。

这道题有两种解法。第一种是模仿p0151的解法每次找到一个完整的单词，得到这个完整单词的头尾坐标，然后根据头尾坐标将这个单词提取出来放入新数组的指定位置。这个解法时间复杂度是O(n)但是空间复杂度同样也是O(n)。

另一种解法是符合follow-up的要求，控制空间复杂度在O(1)并且时间复杂度同样是O(n)。

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

Example:

Input:  ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

Note:

• A word is defined as a sequence of non-space characters.
• The input string does not contain leading or trailing spaces.
• The words are always separated by a single space.

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

首先介绍第一种解法。我们维护一个新的字符数组用于存储翻转后的结果。然后维护两个指针变量，一个是left指针，另一个是right指针。前者是用来定位单词的头位置，后者是用于寻找单词的尾位置。除此之外我们再维护一个end指针用于将单词里的每个字符存储在新数组的指定位置。

我们每次移动right指针寻找到下一个空格或者结尾，从而得到当前的单词的头尾指针。然后从单词末尾开始将字符一个一个填充到新数组的end的指定位置里，每填充一个我们将end指针往前移动一位。填充结束后我们更新left指针为当前right指针后一位，即指向新单词的头位置，然后更新right指针为left指针，这样再重新开始寻找下一个单词，直到所有单词都被提取。

以下是Java的题解代码实现。

class Solution {
    public void reverseWords(char[] s) {
        int L = s.length;
        char[] res = new char[L];
        
        int left = 0, right = 0, end = L-1;
        while (right <= L) {
            while (right < L && s[right] != ' ') {
                ++right;
            }
            
            for (int itr=right-1; itr>=left; --itr) {
                res[end--] = s[itr];
            }
            if (end >= 0)
                res[end--] = ' ';
            
            left = right+1;
            right = left;
        }
        
        for (int idx=0; idx<L; ++idx) {
            s[idx] = res[idx];
        }
    }
}

第二种解法是in-place的，不需要额外维护一个数组来存储结果。如下图所示，

我们可以先翻转整个字符串，然后从前往后对每个单词进行翻转即可。这样一来就可以无需额外空间然后翻转每个字符序列组成的单词。

以下是C++的题解代码实现。

class Solution {
public:
    void reverseWords(vector<char>& s) {
        // First, reverse the whole array
        int N = s.size();
        for (int idx=0; idx<N/2; ++idx) {
            swap(s[idx], s[N-1-idx]);
        }
        
        // Then reverse every word
        int left = 0, right = 0;
        while (right < N) {
            while (right < N && s[right] != ' ') {
                ++right;
            }
            
            int len = right-left;
            for (int idx=0; idx<len/2; ++idx) {
                swap(s[left+idx], s[right-1-idx]);
            }
            
            left = right+1;
            right = left;
        }
    }
};