[LeetCode] 151.Reverse Words in a String 翻轉(zhuǎn)字符串中的單詞

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

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

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

click to show clarification.

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.

這道題讓我們翻轉(zhuǎn)字符串中的單詞，題目中給了我們寫(xiě)特別說(shuō)明，如果單詞之間遇到多個(gè)空格，只能返回一個(gè)，而且首尾不能有單詞，并且對(duì)C語(yǔ)言程序員要求空間復(fù)雜度為O(1)，所以我們只能對(duì)原字符串s之間做修改，而不能聲明新的字符串。那么我們?nèi)绾畏D(zhuǎn)字符串中的單詞呢，我們的做法是，先整個(gè)字符串整體翻轉(zhuǎn)一次，然后再分別翻轉(zhuǎn)每一個(gè)單詞（或者先分別翻轉(zhuǎn)每一個(gè)單詞，然后再整個(gè)字符串整體翻轉(zhuǎn)一次），此時(shí)就能得到我們需要的結(jié)果了。那么這里我們需要定義一些變量來(lái)輔助我們解題，storeIndex表示當(dāng)前存儲(chǔ)到的位置，n為字符串的長(zhǎng)度。我們先給整個(gè)字符串反轉(zhuǎn)一下，然后我們開(kāi)始循環(huán)，遇到空格直接跳過(guò)，如果是非空格字符，我們此時(shí)看storeIndex是否為0，為0的話表示第一個(gè)單詞，不用增加空格；如果不為0，說(shuō)明不是第一個(gè)單詞，需要在單詞中間加一個(gè)空格，然后我們要找到下一個(gè)單詞的結(jié)束位置我們用一個(gè)while循環(huán)來(lái)找下一個(gè)為空格的位置，在此過(guò)程中繼續(xù)覆蓋原字符串，找到結(jié)束位置了，下面就來(lái)翻轉(zhuǎn)這個(gè)單詞，然后更新i為結(jié)尾位置，最后遍歷結(jié)束，我們剪裁原字符串到storeIndex位置，就可以得到我們需要的結(jié)果，代碼如下：

C++ 解法一：

class Solution {
public:
    void reverseWords(string &s) {
        int storeIndex = 0, n = s.size();
        reverse(s.begin(), s.end());
        for (int i = 0; i < n; ++i) {
            if (s[i] != ' ') {
                if (storeIndex != 0) s[storeIndex++] = ' ';
                int j = i;
                while (j < n && s[j] != ' ') s[storeIndex++] = s[j++];
                reverse(s.begin() + storeIndex - (j - i), s.begin() + storeIndex);
                i = j;
            }
        }
        s.resize(storeIndex);
    }
};

Java解法一：

public class Solution {
    public String reverseWords(String s) {
        int storeIndex = 0, n = s.length();
        StringBuilder sb = new StringBuilder(s).reverse();
        for (int i = 0; i < n; ++i) {
            if (sb.charAt(i) != ' ') {
                if (storeIndex != 0) sb.setCharAt(storeIndex++, ' ');
                int j = i;
                while (j < n && sb.charAt(j) != ' ') sb.setCharAt(storeIndex++, sb.charAt(j++));
                String t = new StringBuilder(sb.substring(storeIndex - (j - i), storeIndex)).reverse().toString();
                sb.replace(storeIndex - (j - i), storeIndex, t);
                i = j;
            }
        }
        sb.setLength(storeIndex);
        return sb.toString();
    }
}

下面我們來(lái)看使用字符串流類(lèi)stringstream的解法，我們先把字符串裝載入字符串流中，然后定義一個(gè)臨時(shí)變量tmp，然后把第一個(gè)單詞賦給s，這里需要注意的是，如果含有非空格字符，那么每次>>操作就會(huì)提取連在一起的非空格字符，那么我們每次將其加在s前面即可；如果原字符串為空，那么就不會(huì)進(jìn)入while循環(huán)；如果原字符串為許多空格字符連在一起，那么第一個(gè)>>操作就會(huì)提取出這些空格字符放入s中，然后不進(jìn)入while循環(huán)，這時(shí)候我們只要判斷一下s的首字符是否為空格字符，是的話就將s清空即可，參見(jiàn)代碼如下：

C++ 解法二：

class Solution {
public:
    void reverseWords(string &s) {
        istringstream is(s);
        string tmp;
        is >> s;
        while(is >> tmp) s = tmp + " " + s;
        if(!s.empty() && s[0] == ' ') s = "";
    }
};

下面這種方法也是使用stringstream來(lái)做，但是我們使用了getline來(lái)做，第三個(gè)參數(shù)是設(shè)定分隔字符，我們用空格字符來(lái)分隔，這個(gè)跟上面的>>操作是有不同的，每次只能過(guò)一個(gè)空格字符，如果有多個(gè)空格字符連在一起，那么t會(huì)賦值為空字符串，所以我們?cè)谔幚韙的時(shí)候首先要判斷其是否為空，是的話直接跳過(guò)，參見(jiàn)代碼如下：

C++ 解法三：

class Solution {
public:
    void reverseWords(string &s) {
        istringstream is(s);
        s = "";
        string t = "";
        while (getline(is, t, ' ')) {
            if (t.empty()) continue;
            s = (s.empty() ? t : (t + " " + s));
        }
    }
};

而如果我們使用Java的String的split函數(shù)來(lái)做的話就非常簡(jiǎn)單了，沒(méi)有那么多的幺蛾子，簡(jiǎn)單明了，我們首先將原字符串調(diào)用trim()來(lái)去除冗余空格，然后調(diào)用split()來(lái)分隔，分隔符設(shè)為"\\s+"，這其實(shí)是一個(gè)正則表達(dá)式，\\s表示空格字符，+表示可以有一個(gè)或多個(gè)空格字符，那么我們就可以把單詞分隔開(kāi)裝入一個(gè)字符串?dāng)?shù)組中，然后我們從末尾開(kāi)始，一個(gè)個(gè)把單詞取出來(lái)加入結(jié)果res中，并且單詞之間加上空格字符，注意我們把第一個(gè)單詞留著不取，然后返回的時(shí)候再加上即可，參見(jiàn)代碼如下：

Java解法二：

public class Solution {
    public String reverseWords(String s) {
        String res = "";
        String[] words = s.trim().split("\\s+");
        for (int i = words.length - 1; i > 0; --i) {
            res += words[i] + " ";   
        }
        return res + words[0];
    }
}

下面這種方法就更加的簡(jiǎn)單了，瘋狂的利用到了Java的內(nèi)置函數(shù)，這也是Java的強(qiáng)大之處，注意這里的分隔符沒(méi)有用正則表達(dá)式，而是直接放了個(gè)空格符進(jìn)去，后面還是有+號(hào)，跟上面的寫(xiě)法得到的效果是一樣的，然后我們對(duì)字符串?dāng)?shù)組進(jìn)行翻轉(zhuǎn)，然后調(diào)用join()函數(shù)來(lái)把字符串?dāng)?shù)組拼接成一個(gè)字符串，中間夾上空格符即可，參見(jiàn)代碼如下：

Java解法三：

public class Solution {
    public String reverseWords(String s) {
        String[] words = s.trim().split(" +");
        Collections.reverse(Arrays.asList(words));
        return String.join(" ", words);
    }
}

類(lèi)似題目：

Reverse Words in a String II 

參考資料：

https://discuss.leetcode.com/topic/3298/in-place-simple-solution

https://discuss.leetcode.com/topic/2742/my-accepted-java-solution

https://discuss.leetcode.com/topic/11785/java-3-line-builtin-solution

https://discuss.leetcode.com/topic/10199/5-lines-c-using-stringstream

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