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