0058. Length of Last Word¶
题目信息¶
- 题号:
最后一个单词的长度
- 难度:
Easy
- 主题:
字符串、扫描、双指针
- 原题:
- 重点:
从正向解析全部内容,推导到只扫描包含最后一个单词的必要后缀
题目重述¶
给定一个只包含英文字母和空格的字符串 s,返回最后一个单词的长度。
单词是由连续字母组成的最大非空片段。字符串中至少存在一个单词,单词之间可能有多个空格, 字符串末尾也可能有空格。
约束为 1 <= s.length <= 10^4。
自建示例¶
输入:s = "code review "
输出:6
跳过末尾三个空格后,最后一个单词是 "review"。
输入:s = " x"
输出:1
最后一个单词也是唯一的单词 "x"。
输入:s = "single"
输出:6
字符串没有空格时,整个字符串就是最后一个单词。
C++ 实现¶
#include <sstream>
#include <string>
class Solution {
private:
int parseWithStream(const std::string& s) {
std::istringstream stream(s);
std::string word;
int lastLength = 0;
while (stream >> word) {
lastLength = static_cast<int>(word.size());
}
return lastLength;
}
int scanForward(const std::string& s) {
int currentLength = 0;
int lastLength = 0;
for (char ch : s) {
if (ch == ' ') {
if (currentLength > 0) {
lastLength = currentLength;
currentLength = 0;
}
} else {
++currentLength;
}
}
return currentLength > 0 ? currentLength : lastLength;
}
int scanBackward(const std::string& s) {
int index = static_cast<int>(s.size()) - 1;
while (index >= 0 && s[index] == ' ') {
--index;
}
int length = 0;
while (index >= 0 && s[index] != ' ') {
++length;
--index;
}
return length;
}
public:
int lengthOfLastWord(std::string s) {
return scanBackward(s);
}
};
题解¶
完整单词解析¶
最直接的方法是从左到右读取所有单词,并不断覆盖最近一个单词的长度。
parseWithStream 利用流提取自动跳过连续空格,扫描结束时,lastLength 保存的就是答案。
这种方法直接对应题意,也自然处理开头、结尾和单词之间的多个空格。它仍会解析所有较早单词,
并反复写入临时字符串 word。题目只询问最后一个单词,因此这些前缀内容并不是必要信息。
正向状态压缩¶
去掉字符串流后,可以只维护两个整数:
currentLength = 当前连续字母片段的长度
lastLength = 最近一个已经结束的单词长度
遇到字母时增加 currentLength。遇到空格时,若当前片段非空,就把它提交给
lastLength,再把 currentLength 清零。
扫描结束时存在两种状态:
currentLength > 0:字符串以单词结尾,当前片段就是最后一个单词;currentLength == 0:字符串以空格结尾,答案保存在lastLength中。
scanForward 已把完整单词内容压缩为长度,但从左向右时无法知道后面是否还有新单词,
所以仍必须扫描整个字符串。
必要后缀¶
最后一个单词只与字符串末尾的一段后缀有关:
若干尾部空格 + 最后一个单词
更早的单词和分隔空格不会影响答案。于是扫描方向可以改为从右向左,只处理这段必要后缀:
跳过全部尾部空格,定位最后一个单词的末尾;
继续向左统计连续非空格字符,直到遇到空格或越过字符串开头。
题目保证至少存在一个单词,因此第一阶段结束后,index 一定指向某个字母。
反向扫描不变量¶
第一阶段循环保持:index 右侧已经检查过的字符全部是尾部空格。循环结束时,
s[index] 是字符串最右侧的字母,也就是最后一个单词的最后一个字符。
第二阶段循环保持:已经计数的 length 个字符,恰好是从该最右侧字母向左扩展得到的连续字母后缀。
只要当前字符不是空格,它仍属于同一个单词;一旦遇到空格或数组左边界,这个最大连续片段就结束。
因此第二阶段访问的字符满足:
右侧只有字符串结尾或已经跳过的尾部空格;
内部全部是字母;
左侧是空格或字符串开头。
它正好符合“最后一个单词”的定义,最终 length 就是答案。
状态演化¶
以 "the moon " 为例:
当前字符 |
阶段 |
状态变化 |
|---|---|---|
最后一个空格 |
跳过尾部空格 |
|
前一个空格 |
跳过尾部空格 |
|
|
统计单词 |
|
|
统计单词 |
|
分隔空格 |
结束 |
返回 4 |
边界处理¶
字符串没有尾部空格时,第一阶段不执行,直接从最后一个字母开始计数。
最后一个单词位于字符串开头时,第二阶段最终令 index == -1,计数仍然正确。
只有一个字母时,第二阶段只执行一次。
输入只包含英文字母和普通空格,因此每个输入字符都可由单字节 char 直接判断,
不存在多字节字符长度问题。
复杂度分析¶
字符串流和正向扫描都检查全部 n 个字符,时间为 O(n)。正向扫描使用
O(1) 额外空间;字符串流还维护临时单词和流内部状态。
逆向方法只访问尾部空格和最后一个单词。设这段必要后缀长度为 k,时间为 O(k),
最坏 k = n,因此最坏时间仍为 O(n);额外空间为 O(1)。
公开入口调用 scanBackward,且不修改输入字符串。