151. 翻轉(zhuǎn)字符串里的單詞

題目來(lái)源：https://leetcode-cn.com/problems/reverse-words-in-a-string

題目

給定一個(gè)字符串，逐個(gè)翻轉(zhuǎn)字符串中的每個(gè)單詞。

示例 1：

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

示例 2：

輸入: "  hello world!  "
輸出: "world! hello"
解釋: 輸入字符串可以在前面或者后面包含多余的空格，但是反轉(zhuǎn)后的字符不能包括。

示例 3：

輸入: "a good   example"
輸出: "example good a"
解釋: 如果兩個(gè)單詞間有多余的空格，將反轉(zhuǎn)后單詞間的空格減少到只含一個(gè)。

說明：

• 無(wú)空格字符構(gòu)成一個(gè)單詞。
• 輸入字符串可以在前面或者后面包含多余的空格，但是反轉(zhuǎn)后的字符不能包括。
• 如果兩個(gè)單詞間有多余的空格，將反轉(zhuǎn)后單詞間的空格減少到只含一個(gè)。

解題思路

思路一：利用語(yǔ)言特性

python 語(yǔ)言中提供 split 切割，join 連接等方法，可以直接調(diào)用內(nèi)置方法解決該問題。

具體的步驟：

• 使用 spilt 將字符進(jìn)行切割，得到字符串列表
• 使用切片操作反轉(zhuǎn)字符串列表
• 使用 join 將反轉(zhuǎn)后的字符串列表用空格拼接。

當(dāng)用此方法編寫代碼完成后，可以考慮自己編寫函數(shù)實(shí)現(xiàn)，或者換其他思路實(shí)現(xiàn)。

思路二：雙指針

因?yàn)樽罱K結(jié)果需要數(shù)組進(jìn)行倒序后輸出，所以在尾部進(jìn)行雙指針定義，倒序遍歷數(shù)組。

題目中說明【無(wú)空格字符構(gòu)成一個(gè)單詞】。那么按照這個(gè)原則，確定單詞邊界，將單詞添加到定義的列表中。

最終的步驟也是將單詞列表拼接返回。

具體過程如下圖：

雙指針 | 圖解

代碼實(shí)現(xiàn)

語(yǔ)言特性：代碼實(shí)現(xiàn)

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

雙指針：代碼實(shí)現(xiàn)

class Solution:
    def reverseWords(self, s: str) -> str:
        # 尾部定義指針
        p = len(s) - 1
        # 定義返回結(jié)果
        ans = []

        while p >= 0:
            # 倒序遍歷，這里先去除尾部空格
            while p >= 0 and s[p] == ' ':
                p -= 1
            # 重置指針
            q = p
            # 這一步防止開頭存在空格，
            # 最終卻把空格添加到返回結(jié)果中
            if q < 0:
                break
            # 確定單詞邊界
            while p >= 0 and s[p] != ' ':
                p -= 1
            # 將單詞放到結(jié)果中
            ans.append(s[p + 1:q + 1])
        # 拼接返回結(jié)果
        return ' '.join(ans)

實(shí)現(xiàn)結(jié)果

語(yǔ)言特性：實(shí)現(xiàn)結(jié)果

語(yǔ)言特性 | 實(shí)現(xiàn)結(jié)果

雙指針：實(shí)現(xiàn)結(jié)果

雙指針 | 實(shí)現(xiàn)結(jié)果

以上就是使用語(yǔ)言特性，或者使用雙指針的方法來(lái)解決《151. 翻轉(zhuǎn)字符串里的單詞》問題的主要內(nèi)容。

歡迎關(guān)注微信公眾號(hào)《書所集錄》