【Leetcode之字元串】0151 翻轉字元串裡的單詞

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/reverse-words-in-a-string

實作語言：Java

目錄

• • 題目
  • 方法：兩次翻轉

題目

給定一個字元串，逐個翻轉字元串中的每個單詞。

說明：

• 無空格字元構成一個 單詞 。
• 輸入字元串可以在前面或者後面包含多餘的空格，但是反轉後的字元不能包括。
• 如果兩個單詞間有多餘的空格，将反轉後單詞間的空格減少到隻含一個。

示例

輸入："the sky is blue"
輸出："blue is sky the"

輸入："  hello world!  "
輸出："world! hello"
解釋：輸入字元串可以在前面或者後面包含多餘的空格，但是反轉後的字元不能包括。

輸入："a good   example"
輸出："example good a"
解釋：如果兩個單詞間有多餘的空格，将反轉後單詞間的空格減少到隻含一個。

輸入：s = "  Bob    Loves  Alice   "
輸出："Alice Loves Bob"

輸入：s = "Alice does not even like bob"
輸出："bob like even not does Alice"
           

提示：

1. 1 <= S.length <= 20000

2. S

   僅由小寫英文字母組成。

方法：兩次翻轉

代碼實作

class Solution {
    public String reverseWords(String s) {
        // 删除多餘的空格。" {1,}" 正規表達式，至少比對一個空格 
        s = s.trim();  // 删除首尾空格
        String[] str = s.split(" {1,}");
        String res = "";
        // 逐一翻轉單個單詞
        for (int i=0; i<str.length; i++) {
            str[i] = reverseOneWord(str[i]);
            res += str[i];
            if (i!=str.length-1) res += " ";
        }
        // 翻轉全部字元串
        res = reverseOneWord(res);     
        return res;
    }
    // 翻轉一個單詞
    public static String reverseOneWord(String s) {
		char[] str = s.toCharArray();
        char tmp;
        for (int i=0,j=str.length-1; i<j; i++,j--) {
            tmp = str[j];
            str[j] = str[i];
            str[i] = tmp;
        }
        return new String(str);
    }
}
           

時間複雜度：O( n )

空間複雜度：O( n )

執行用時：17 ms

記憶體消耗：39.3 MB