[LeetCode]151. 翻轉字元串裡的單詞

題目

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

示例 1：

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

示例 2：

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

示例 3：

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

說明：

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

進階：

請選用 C 語言的使用者嘗試使用 O(1) 額外空間複雜度的原地解法。

解題思路

解法一：調用内置API

1）使用 split 将字元串按空格分割成字元串數組；

2）使用 reverse 将字元串數組進行反轉；

3）使用 join 方法将字元串數組拼成一個字元串。

複雜度分析：

時間複雜度：O(N)，其中 N 為輸入字元串的長度。

空間複雜度：O(N)，用來存儲字元串分割之後的結果。

解法二：自行編寫函數實作（雙指針法）

主要思路是：

1）倒序周遊字元串 s ，記錄單詞左右索引邊界i,j；

2）每确定一個單詞的邊界，則将其添加至單詞清單 res；

3）将單詞清單拼接為字元串。

詳細步驟如下：

1）首先删除字元串首尾空格；

2）令i,j都指向字元串末尾，即 i=j=len(s)-1

3）當i>=0時，循環：

3.1）i向左周遊，當i遇到空格時，将單詞s[i+1:j+1]添加至res；

3.2）i繼續向左周遊，跳過兩單詞間的所有空格，直到遇到字元，令j=i，此時j指向新單詞的末尾。

4）将res以空格拼接，并傳回。

複雜度分析：

時間複雜度 O(N)：其中 N 為字元串 s 的長度。

空間複雜度 O(N)：需要 O(N) 大小的額外空間。

代碼

解法一：調用API

class Solution:
    def reverseWords(self, s: str) -> str:
        # return ' '.join(s.split()[::-1])
        return ' '.join(reversed(s.split()))
           

解法二：雙指針

class Solution:
    def reverseWords(self, s: str) -> str:
        # 删除字元串的首尾空格
        s = s.strip()
        i = j = len(s)-1
        res = []
        while i>=0:
            while i>=0 and s[i] != ' ': # 搜尋空格
                i -= 1
            res.append(s[i+1:j+1]) # 添加單詞到res
            while i>=0 and s[i] == ' ': # 跳過兩單詞間的空格
                i -= 1
            j = i # 指向新單詞的末尾
        return ' '.join(res)