LeetCode 58 最後一個單詞長度：雙指針倒序遍歷

問題描述

給定字符串 s（含大小寫字母和空格），返回最後一個單詞的長度。單詞定義為不含空格的字符序列。若不存在返回 0。例如 "Hello World" → 5。

算法思路

從字符串末尾向前掃描：

1. 跳過尾部空格
2. 計數非空格字符直到遇到空格或開頭

優化實現（C++）

class Solution {
public:
    int lengthOfLastWord(const char* s) {
        int len = strlen(s);
        int i = len - 1;
        // 跳過尾部空格
        while (i >= 0 && s[i] == ' ') --i;
        // 計數單詞長度
        int lastLen = 0;
        while (i >= 0 && s[i] != ' ') {
            ++lastLen;
            --i;
        }
        return lastLen;
    }
};

關鍵點

• 處理全空格、尾部空格、單詞中間空格等邊界情況
• 時間複雜度 O(n)，空間 O(1)
• 不使用額外庫函數（如 `stringstream`），效率最高

擴展：C++ string 版本

int lengthOfLastWord(string s) {
    int i = s.size() - 1;
    while (i >= 0 && s[i] == ' ') --i;
    int end = i;
    while (i >= 0 && s[i] != ' ') --i;
    return end - i;
}

此題考察基本字符串處理與邊界條件控制，是面試熱身題的典型代表。