58. 最后一个单词的长度

题目

力扣题目

给你一个字符串 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
解释：最后一个单词是 "joyboy"，长度为 6。

提示：

• 1 <= s.length <= 10^4
• s 仅由英文字母和空格 ' ' 组成
• s 中至少存在一个单词

考察内容

• 字符串下标访问
• 从后向前遍历字符串
• 跳过末尾空格
• 识别单词的边界
• 有符号与无符号下标的转换

解题思路

反向遍历

题目只关心最后一个单词，因此没有必要从头解析所有单词。从字符串末尾开始向前扫描即可：

1. 从最后一个字符开始，跳过所有末尾空格；
2. 此时指针位于最后一个单词的末尾；
3. 继续向前移动，只要当前字符不是空格，就累加单词长度；
4. 遇到空格或移动到字符串左侧之外时结束。

以 s = " fly me to the moon " 为例：

• 先跳过末尾的两个空格；
• 指针到达字符 'n'；
• 依次统计 'n'、'o'、'o'、'm'；
• 遇到 moon 前面的空格，返回长度 4。

循环结束时，length 恰好等于最后一个单词包含的字符数量。

• 时间复杂度：$O(n)$。最坏情况下需要从字符串末尾扫描到开头；实际只扫描末尾空格和最后一个单词。
• 空间复杂度：$O(1)$。

正向遍历

也可以从左向右扫描：遇到非空格字符时，如果前一个字符是空格，则说明进入了新单词，将当前长度重置为 1；否则继续累加。最后保留的长度就是最后一个单词的长度。

这种写法同样是 $O(n)$ 时间、$O(1)$ 空间，但会扫描整个字符串。只关心最后一个单词时，反向遍历更直接。

代码演示

int lengthOfLastWord(const std::string& s) {
    int i = static_cast<int>(s.size()) - 1;

    // 第一步：跳过字符串末尾的空格
    while (i >= 0 && s[i] == ' ') {
        --i;
    }

    // 第二步：统计最后一个单词的长度
    int length = 0;
    while (i >= 0 && s[i] != ' ') {
        ++length;
        --i;
    }

    return length;
}

易错点

• 没有跳过末尾空格：字符串可能以多个空格结尾，直接开始计数会得到 0。
• 先统计再跳过空格：正确顺序是先定位最后一个非空格字符，再统计单词长度。
• 扫描到第一个空格就结束：从字符串末尾开始时，首先遇到的可能是末尾空格，必须先跳过它们。
• 下标越界：两个 while 条件都应先检查 i >= 0，再访问 s[i]。
• 无符号下溢：s.size() 返回无符号类型。若直接使用无符号下标并递减到 0 以下，会产生下溢；这里先转换为 int。
• 不必要地拆分字符串：使用 stringstream 或创建单词数组可以完成题目，但需要额外空间，也解析了不需要的前置单词。

总结

这道题的关键是利用“只需要最后一个单词”这一条件，从字符串末尾反向处理：

1. 跳过末尾空格；
2. 统计连续的非空格字符；
3. 遇到空格或字符串开头后结束。

反向遍历无需切分字符串，也无需保存其他单词，只使用常数额外空间。

相关题目

• 151. 反转字符串中的单词
• 344. 反转字符串
• 345. 反转字符串中的元音字母
• 557. 反转字符串中的单词 III
• 1816. 截断句子