58. Length of Last Word

題目 / Problem

中文： 給定一個由單字與空格組成的字串 s，請回傳字串中最後一個單字的長度。一個「單字」是指由非空格字元組成的最長子字串。

English: Given a string s consisting of words and spaces, return the length of the last word in the string. A word is a maximal substring consisting of non-space characters only.

Constraints： - 1 <= s.length <= 10^4 - s 只包含英文字母與空格 ' ' / s consists of only English letters and spaces. - 至少會有一個單字 / There will be at least one word in s.

Worked example: - Input: s = " fly me to the moon " - Output: 4 - Explanation: 最後一個單字是 "moon"，長度為 4 / The last word is "moon" with length 4. 注意末尾還有空格要先跳過 / Note the trailing spaces must be skipped first.

名詞解釋 / Glossary

• 字串 / string：在 C 裡是以 \0 結尾的字元陣列 (char *)；在 C++ 裡通常用 std::string 類別。 / In C a string is a \0-terminated char array; in C++ we usually use the std::string class.
• 索引 / index：陣列中元素的位置編號，從 0 開始。 / The numerical position of an element in an array, starting at 0.
• 從尾端掃描 / scan from the end：從字串最後一個字元開始往前走，而不是從頭開始。對於「找最後一個 X」的問題非常有效率，因為一旦找到就能立即停下。 / Walk the string from the last character backward to the front. Efficient for "find the last X" problems because we can stop as soon as we find it.
• 空格 / whitespace character：這題只會出現 ASCII 半形空格 ' ' (值為 32)。 / In this problem, only the ASCII space character ' ' (value 32) appears.
• strlen：C 標準函式，回傳字串中 \0 之前的字元數，時間複雜度為 O(n)。 / Standard C function that returns the number of characters before the terminating \0; runs in O(n).
• size_t：C/C++ 中用來表示「大小或長度」的無號整數型別。 / An unsigned integer type used for sizes and lengths in C/C++.

思路

最直覺的暴力做法是：先用空格把整個字串切成許多單字，存進一個陣列，再取最後一個單字計算長度。這個方法可行，但要額外分配記憶體，而且我們其實只需要「最後一個單字」，把整個字串都切開就太浪費了。更好的方法是從字串的尾端往前掃：先跳過末尾連續的空格(像 "...moon " 結尾有兩個空格)，找到最後一個非空格字元的位置；然後再繼續往前走，數出有幾個連續的非空格字元，直到碰到空格或走出字串為止。這個計數就是答案。整個過程只走一遍字串的一部分，不需要額外空間，是最理想的線性時間解。關鍵不變量是：當我們從尾端跳完空格後，當前指到的字元一定屬於最後一個單字；接著只要持續往前走並計數，就能準確得到該單字的長度。

The brute-force idea would be to split the whole string by spaces into a list of words and then take the length of the last one. That works but allocates extra memory just to throw most of it away — we only care about one word. A better approach scans from the end of the string toward the front. First, skip any trailing spaces (e.g., the two spaces at the end of "...moon "); the index now points to the last character of the last word. Then keep moving left, incrementing a counter, until we either fall off the start of the string or hit another space. That counter is the answer. We touch at most O(n) characters once and need no extra memory. The key invariant is: after skipping trailing spaces, the current index is guaranteed to lie inside the last word, so the subsequent count gives exactly its length.

逐步走查 / Walkthrough

Input: s = " fly me to the moon " (length 27, indices 0..26)

最終回傳 length = 4 / Return length = 4. ✅

Solution — C

/*
 * 演算法 / Algorithm:
 *   1. 從字串尾端往前掃，先跳過所有結尾的空格。
 *      Scan from the end, skipping all trailing spaces first.
 *   2. 接著一邊往前走一邊計數，直到碰到空格或走到字串開頭。
 *      Then count non-space chars walking left until a space or start of string.
 */

#include <string.h>  // 引入 strlen / include strlen

int lengthOfLastWord(char* s) {
    // strlen 回傳 '' 之前的字元數；型別是 size_t (無號)
    // strlen returns the number of chars before ''; its type is size_t (unsigned)
    int i = (int)strlen(s) - 1;  // i 指向最後一個字元 / i points to the last character

    // 第一個迴圈：跳過末尾的空格
    // First loop: skip trailing spaces
    // 條件 i >= 0 防止走出字串左邊界 / i >= 0 guards against falling off the left end
    while (i >= 0 && s[i] == ' ') {
        i--;  // 往左移一格 / move one step left
    }

    int length = 0;  // 累計最後一個單字的長度 / counter for the last word's length

    // 第二個迴圈：從最後一個字元往前數，直到再次遇到空格
    // Second loop: count characters going left until we meet another space
    while (i >= 0 && s[i] != ' ') {
        length++;  // 又數到一個非空格字元 / found one more non-space character
        i--;       // 繼續往左 / keep moving left
    }

    return length;  // 回傳答案 / return the result
}

Solution — C++

/*
 * 演算法 / Algorithm:
 *   與 C 解法相同：從尾端向前跳過空格，再向前計數最後一個單字長度。
 *   Same as the C solution: skip trailing spaces from the end, then count
 *   the length of the last word while walking left.
 */

#include <string>  // 使用 std::string / use std::string

class Solution {
public:
    // 參數用 const std::string& 傳參考，避免複製整個字串
    // Pass by const reference to avoid copying the whole string
    int lengthOfLastWord(const std::string& s) {
        // int 可放下 10^4，安全 / int can hold 10^4 safely
        // s.size() 回傳 size_t (無號)，所以先轉成 int 才能變負
        // s.size() returns size_t (unsigned); cast to int so it can go negative
        int i = static_cast<int>(s.size()) - 1;  // 從最後一個索引開始 / start at last index

        // 跳過結尾空格 / skip trailing spaces
        while (i >= 0 && s[i] == ' ') {
            --i;  // 前綴 -- 比後綴 -- 略有效率，效果相同 / pre-decrement, same effect
        }

        int length = 0;  // 計數器 / counter

        // 數出最後一個單字的長度 / count the length of the last word
        while (i >= 0 && s[i] != ' ') {
            ++length;  // 每碰到一個非空格就 +1 / +1 for each non-space char
            --i;       // 往左移 / move left
        }

        return length;  // 回傳結果 / return the answer
    }
};

複雜度 / Complexity

• Time: O(n) — n 是字串長度 s.length。最壞情況下我們從尾端走到頭(例如整個字串只有一個單字)，但每個字元只被造訪一次。 / n is s.length. In the worst case we traverse from end to start (e.g., a string with one long word), but each character is visited at most once.
• Space: O(1) — 只用了兩個整數變數 i 與 length，與輸入大小無關。 / Only two integer variables (i and length) are used; memory does not grow with input size.

Pitfalls & Edge Cases

• 末尾空格 / Trailing spaces：像 "Hello World " 不能一拿到字串就從最後一個字元開始計數，會數到 0。必須先跳過空格。 / You can't just count from the very last character — strings like "Hello World " end in spaces and would give 0. Skip them first.
• 整個字串只有一個單字 / Single-word input：如 "abc"，第一個迴圈不會執行，第二個迴圈會一路掃到 i = -1 才停。i >= 0 的邊界檢查就是為此而設。 / For inputs like "abc", the skip loop runs zero times and the count loop walks all the way to i = -1. The i >= 0 guard prevents reading out of bounds.
• 無號型別陷阱 / Unsigned-type trap：strlen 與 std::string::size() 都回傳無號型別。若直接 size_t i = s.size() - 1 並用 i >= 0 當條件，會永遠成立而造成無窮迴圈或越界。本解法把長度轉成 int 後再減 1。 / Both strlen and s.size() return unsigned types. Writing size_t i = s.size() - 1 with an i >= 0 test creates an infinite loop because unsigned values are never negative. We cast to int before subtracting.
• 題目保證至少一個單字 / At-least-one-word guarantee：所以不必處理「整個字串都是空格」的情況；不過上面的程式碼即使遇到那種輸入也會安全地回傳 0。 / The constraints guarantee at least one word, so we don't need to handle an all-spaces string — though the code above would still safely return 0 if given one.
• 只看 ' ' 一種空格 / Only ASCII space：題目保證只會出現英文字母與半形空格，不必處理 \t、\n 等其他空白字元。 / The problem guarantees only English letters and the ASCII space, so we don't need to handle \t, \n, or other whitespace.