【題目】

給你一個字符串 s，由若干單詞組成，單詞前后用一些空格字符隔開。返回字符串中 最后一個 單詞的長度。

單詞 是指僅由字母組成、不包含任何空格字符的最大子字符串。

示例 1：

輸入： s = "Hello World"
輸出： 5
解釋： 最后一個單詞是“World”，長度為5。

示例 2：

輸入： s = "   fly me   to   the moon  "
輸出： 4 解釋： 最后一個單詞是“moon”，長度為4。

示例 3：

輸入： s = "luffy is still joyboy"
輸出： 6
解釋： 最后一個單詞是長度為6的“joyboy”。

提示：

• 1 <= s.length <=
• s 僅有英文字母和空格 ' ' 組成
• s 中至少存在一個單詞

【題目解析】

解題方法

本問題的核心在于如何快速定位到字符串中的最后一個單詞，并計算其長度。為此，我們采取的方法是逆向遍歷字符串。具體步驟如下：

1. 從字符串的末尾開始向前遍歷，首先跳過所有的空格字符，以找到最后一個單詞的末尾。
2. 繼續(xù)遍歷，直到遇到另一個空格或字符串的開頭，計算這個過程中遍歷的字符數(shù)量，即為最后一個單詞的長度。

這個方法避免了對字符串的全面掃描，尤其是當(dāng)最后一個單詞之前有大量空格時，可以顯著提高效率。

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        length = 0
        index = len(s) - 1
        
        # 跳過末尾的空格
        while index >= 0 and s[index] == ' ':
            index -= 1
        
        # 計算最后一個單詞的長度
        while index >= 0 and s[index] != ' ':
            length += 1
            index -= 1
        
        return length

執(zhí)行效率

image.png

【總結(jié)】

適用問題類型

• 字符串處理問題：特別是那些需要從字符串的尾部開始分析或提取信息的問題，如反轉(zhuǎn)字符串、找到最后一個特定字符或單詞的位置等。
• 文本分析：在處理自然語言文本、日志文件等含有大量單詞或條目的字符串時，這種方法同樣適用。

解決算法：逆向遍歷

• 算法描述：從字符串的末尾開始，逆向遍歷整個字符串，通過特定的條件判斷來實現(xiàn)對字符串尾部信息的提取或分析。

• 關(guān)鍵步驟：

  1. 識別并跳過尾部無關(guān)字符（如空格）。
  2. 計算并提取所需信息（如最后一個單詞的長度）。
  3. 在遇到分隔符或字符串開始處停止遍歷。

算法特點

• 高效性：能夠直接定位到關(guān)鍵信息的位置，避免了對整個字符串的全面掃描。
• 簡潔性：代碼實現(xiàn)簡單，邏輯清晰易懂。
• 通用性：適用于各種需要從尾部處理字符串的場景。

時間復(fù)雜度與空間復(fù)雜度

• 時間復(fù)雜度：O(N)，其中N是字符串的長度。在最壞的情況下，算法需要遍歷整個字符串一次。
• 空間復(fù)雜度：O(1)，算法運行過程中僅使用了常數(shù)級別的額外空間。

實踐意義

• 編程技巧提升：掌握逆向遍歷字符串的方法有助于提高解決字符串處理問題的能力，尤其是在面對性能優(yōu)化需求時。
• 算法思維培養(yǎng)：通過逆向思考問題，尋找解決問題的高效路徑，有助于培養(yǎng)解決復(fù)雜問題的算法思維。
• 廣泛的應(yīng)用場景：在文本分析、日志處理、數(shù)據(jù)清洗等領(lǐng)域，逆向遍歷字符串的方法都有其獨特的應(yīng)用價值。

綜上所述，通過逆向遍歷字符串解決"最后一個單詞的長度"問題，不僅展示了一種高效的算法實現(xiàn)，也提供了一種值得學(xué)習(xí)的編程技巧和思維方式，對于提升編程實踐能力具有重要的意義。

題目鏈接

最后一個單詞的長度