leetcode 151. Reverse Words in a String

yzd 發(fā)布于2019-08-16 10:40 / 3447人閱讀

摘要：題目要求講一個字符串中的單詞逆序輸出，單詞中字母順序不發(fā)生改變。其中，字符串首位的空格應(yīng)刪去，字符串中如果存在多余的空格，只需輸出一個空格。這里用到的正則表達(dá)式為也就是遇到一個或多個空白時斷句。

題目要求

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.

講一個字符串中的單詞逆序輸出，單詞中字母順序不發(fā)生改變。其中，字符串首位的空格應(yīng)刪去，字符串中如果存在多余的空格，只需輸出一個空格。

思路一：正則表達(dá)式

關(guān)于正則表達(dá)式的詳細(xì)信息，請參考我的這篇博客
在這里，我們只需要將句子中的單詞通過split的正則表達(dá)式讀取出來即可。這里用到的正則表達(dá)式為s+,也就是遇到一個或多個空白時斷句。

    public String reverseWords(String s) {
        String[] array = s.trim().split("s+");
        String result = "";
        for(int i = array.length-1 ; i>0 ; i--){
            result += array[i] + " ";
        }
        return result + array[0];
    }

思路二：雙指針

其實(shí)雙指針這里也用了String的API，不過核心的思路還是在于通過雙指針找到一個單詞的位置，然后通過獲得子字符串的方法將其提取出來加入到結(jié)果集中。

    public String reverseWords(String s){
        String trimmed = s.trim();
        int prev = trimmed.length();
        int index = prev;
        StringBuilder result = new StringBuilder();
        while ((index = trimmed.lastIndexOf(" ", index-1)) > 0) {
            if (index < prev-1) {
                result.append(trimmed.substring(index+1, prev));
                result.append(" ");
            }
            prev = index;
        }
        result.append(trimmed.substring(index+1, prev));
        return result.toString();
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~