[LeetCode] 186. Reverse Words in a String II 翻轉(zhuǎ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?

這道題讓我們翻轉(zhuǎn)一個字符串中的單詞，跟之前那題 Reverse Words in a String 沒有區(qū)別，由于之前那道題就是用 in-place 的方法做的，而這道題反而更簡化了題目，因為不考慮首尾空格了和單詞之間的多空格了，方法還是很簡單，先把每個單詞翻轉(zhuǎn)一遍，再把整個字符串翻轉(zhuǎn)一遍，或者也可以調(diào)換個順序，先翻轉(zhuǎn)整個字符串，再翻轉(zhuǎn)每個單詞，參見代碼如下：

解法一：

class Solution {
public:
    void reverseWords(vector<char>& str) {
        int left = 0, n = str.size();
        for (int i = 0; i <= n; ++i) {
            if (i == n || str[i] == ' ') {
                reverse(str, left, i - 1);
                left = i + 1;
            }
        }
        reverse(str, 0, n - 1);
    }
    void reverse(vector<char>& str, int left, int right) {
        while (left < right) {
            char t = str[left];
            str[left] = str[right];
            str[right] = t;
            ++left; --right;
        }
    }
};

我們也可以使用 C++ STL 中自帶的 reverse 函數(shù)來做，先把整個字符串翻轉(zhuǎn)一下，然后再來掃描每個字符，用兩個指針，一個指向開頭，另一個開始遍歷，遇到空格停止，這樣兩個指針之間就確定了一個單詞的范圍，直接調(diào)用 reverse 函數(shù)翻轉(zhuǎn)，然后移動頭指針到下一個位置，在用另一個指針繼續(xù)掃描，重復(fù)上述步驟即可，參見代碼如下：

解法二：

class Solution {
public:
    void reverseWords(vector<char>& str) {
        reverse(str.begin(), str.end());
        for (int i = 0, j = 0; i < str.size(); i = j + 1) {
            for (j = i; j < str.size(); ++j) {
                if (str[j] == ' ') break;
            }
            reverse(str.begin() + i, str.begin() + j);
        }
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/186

類似題目：

Reverse Words in a String III

Reverse Words in a String

Rotate Array

參考資料：

https://leetcode.com/problems/reverse-words-in-a-string-ii/

https://leetcode.com/problems/reverse-words-in-a-string-ii/discuss/53851/Six-lines-solution-in-C%2B%2B

https://leetcode.com/problems/reverse-words-in-a-string-ii/discuss/53775/My-Java-solution-with-explanation

到此這篇關(guān)于C++實現(xiàn)LeetCode(186.翻轉(zhuǎn)字符串中的單詞之二)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)翻轉(zhuǎn)字符串中的單詞之二內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論