bigywater.tech
算法与数据结构 · LeetCode 58

LeetCode 58. 最后一个单词的长度

给定一个由单词和空格组成的字符串,返回最后一个单词的长度。单词是只含字母、被空格分隔的字符串,并且字符串开头和结尾都可能有多余的空格。最直观的写法是按空格切分再取最后一段,但这里有一个陷阱:结尾有空格时,按单个空格切分会得到一个空字符串。更好的做法是从字符串末尾往回扫:先跳过结尾的空格,再数最后一个单词的字符,遇到空格或者到达开头就停。本文用真实运行展示切分写法的陷阱,实测两种写法在长字符串上的耗时,给出五种语言的实现,并把从右往左的扫描做成分步演示。

20,000
组随机对拍,与暴力解的结果全部一致
8 步
分步演示,每一帧都来自解法的真实执行,另附 5 种语言实现

题意与示例

完整题目见官方页面(链接在文末)。字符串里至少有一个单词。基准解是 s.split()[-1]:按任意连续空白切分,取最后一段的长度,与从后往前扫描是两种写法。一共 12 组用例,覆盖:官方示例、结尾有空格、开头有空格、首尾都有空格、只有一个单词、单词之间有多个空格:

真实实测 · 本机执行输出
输入 ["Hello World"]
输出 5
输入 ["   fly me   to   the moon  "]
输出 4
输入 ["luffy is still joyboy"]
输出 6
输入 ["a"]
输出 1
输入 ["a "]
输出 1
输入 [" a"]
输出 1

陷阱:split(' ') 会在结尾产生空字符串

Python 里 s.split()(不带参数)会把连续的空白当成一个分隔符,并忽略首尾的空白;而 s.split(' ')(指定按单个空格切分)会保留每一个空格之间的空字符串。所以结尾有空格时,split(' ')[-1] 是空字符串。下面是真实结果:

真实实测 · 本机执行输出
# 用 split(' ') 切分,取最后一段
'Hello World': split(' ')[-1] = 'World',长度 5    split()[-1] 长度 5    solve -> 5
'Hello World  ': split(' ')[-1] = '',长度 0    split()[-1] 长度 5    solve -> 5
'   fly me   to   the moon  ': split(' ')[-1] = '',长度 0    split()[-1] 长度 4    solve -> 4

'Hello World ' 结尾有两个空格,split(' ')[-1] 是空字符串,长度 0,而正确答案是 5。第一行没有结尾空格,两种写法碰巧一致。Java 的 split(" ") 会丢掉结尾的空字符串,行为与 Python 不同,这里没有实测;从后往前扫描的写法不依赖各语言的切分规则,五种语言写法一致。

从后往前扫描:五种语言的实现

i 从最后一个字符开始。第一个循环:只要 s[i] 是空格就往左走,跳过结尾的空格。第二个循环:只要 s[i] 不是空格就长度加一、往左走;遇到空格或者走出开头就停。返回长度。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。

Python · 解法代码def solve(s): i = len(s) - 1 while i >= 0 and s[i] == " ": # 先跳过末尾的空格 i -= 1 length = 0 while i >= 0 and s[i] != " ": # 再数最后一个单词的字符,遇到空格或开头停 length += 1 i -= 1 return length
真实实测 · Python · 前几组用例的输出
$ python3 solution.py   # 统一入口:逐行读取 cases.jsonl,调用上面的 solve,打印 JSON
["Hello World"]  →  5
["   fly me   to   the moon  "]  →  4
["luffy is still joyboy"]  →  6
["a"]  →  1
["a "]  →  1
[" a"]  →  1
Java · 解法代码class Solution { public int lengthOfLastWord(String s) { int i = s.length() - 1; while (i >= 0 && s.charAt(i) == ' ') i--; // 先跳过末尾的空格 int length = 0; while (i >= 0 && s.charAt(i) != ' ') { // 再数最后一个单词的字符,遇到空格或开头停 length++; i--; } return length; } }
真实实测 · Java · 前几组用例的输出
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl
["Hello World"]  →  5
["   fly me   to   the moon  "]  →  4
["luffy is still joyboy"]  →  6
["a"]  →  1
["a "]  →  1
[" a"]  →  1
Go · 解法代码func lengthOfLastWord(s string) int { i := len(s) - 1 for i >= 0 && s[i] == ' ' { // 先跳过末尾的空格 i-- } length := 0 for i >= 0 && s[i] != ' ' { // 再数最后一个单词的字符,遇到空格或开头停 length++ i-- } return length }
真实实测 · Go · 前几组用例的输出
$ go build -o bin . && ./bin < cases.jsonl
["Hello World"]  →  5
["   fly me   to   the moon  "]  →  4
["luffy is still joyboy"]  →  6
["a"]  →  1
["a "]  →  1
[" a"]  →  1
JavaScript · 解法代码function lengthOfLastWord(s) { let i = s.length - 1; while (i >= 0 && s[i] === " ") i--; // 先跳过末尾的空格 let length = 0; while (i >= 0 && s[i] !== " ") { // 再数最后一个单词的字符,遇到空格或开头停 length++; i--; } return length; }
真实实测 · JavaScript · 前几组用例的输出
$ node run.js < cases.jsonl
["Hello World"]  →  5
["   fly me   to   the moon  "]  →  4
["luffy is still joyboy"]  →  6
["a"]  →  1
["a "]  →  1
[" a"]  →  1
C++ · 解法代码#include <string> using namespace std; class Solution { public: int lengthOfLastWord(string s) { int i = (int)s.size() - 1; while (i >= 0 && s[i] == ' ') i--; // 先跳过末尾的空格 int length = 0; while (i >= 0 && s[i] != ' ') { // 再数最后一个单词的字符,遇到空格或开头停 length++; i--; } return length; } };
真实实测 · C++ · 前几组用例的输出
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl
["Hello World"]  →  5
["   fly me   to   the moon  "]  →  4
["luffy is still joyboy"]  →  6
["a"]  →  1
["a "]  →  1
[" a"]  →  1
真实实测 · 本机执行输出
共 12 组用例(含边界),以暴力解的结果为基准逐组比对:
  Python      通过 12/12
  Java        通过 12/12
  Go          通过 12/12
  JavaScript  通过 12/12
  C++         通过 12/12

耗时实测:只看末尾,不看全部

切分要扫描整个字符串,而从后往前扫描只看末尾的几个字符,与字符串总长度无关。我构造了很长的字符串(前面是大量的短单词,末尾有 3 个空格),在 Python 里比较两种写法,每个取三次中最快的一次:

真实实测 · 本机执行输出
长度为 n 的字符串(很多个单词,最后一个单词长 5,后面有 3 个空格):从后往前扫描 vs split 后取最后一个(各取三次中最快)
n=  100000: 从后往前扫描   0.0006 ms(结果 7)    split 后取最后     0.493 ms(结果 7)
n= 1000000: 从后往前扫描   0.0005 ms(结果 7)    split 后取最后     6.711 ms(结果 7)
n=10000000: 从后往前扫描   0.0005 ms(结果 7)    split 后取最后    86.387 ms(结果 7)

从后往前扫描的耗时始终是 0.0005 毫秒左右,不随字符串长度变化;split 的耗时随长度线性增长,长度 1000 万时用了 86.4ms。表中的结果都是 7,也就是最后一个单词的长度是 7(构造字符串时,"hello" 前面残留的字符与它连在了一起,两种写法算出的结果一致)。split 版本是 C 实现,所以 10 万个字符时也只要 0.5ms,两者的差别只有在字符串很长时才有意义。

随机对拍

Python 版本另外和 split()[-1] 做了随机对拍,字符串由 1 到 4 个 a、b 组成的单词构成,单词之间、首尾有随机数量的空格:

真实实测 · 本机执行输出
随机对拍 20000 组(1 到 4 个由 a、b 组成的单词,单词之间和首尾随机加 0 到 3 个空格(至少有一个单词)),solve 与 brute 的结果全部一致。

另外四种语言只在上面 12 组固定用例上验证过,没有做大规模随机对拍。

分步演示:从右往左

下面的演示用 "fly me to the moon "(结尾有两个空格,字符串里 ␣ 表示空格)。先跳过结尾的两个空格(淡色),再数最后一个单词 moon 的四个字符,遇到前面的空格停止,答案是 4。每一帧都是把上面的解法在这组输入上真实执行记录下来的,运行器还检查了演示的最终结果与 solve 的返回值一致。

最后一个单词的长度:"fly me to the moon "(␣ 表示空格)
末尾被跳过的空格当前字符最后一个单词的字符

    参考与说明

    • 官方题目页:LeetCode 58. 最后一个单词的长度。本文只用自己的话概括了题意,完整约束以官方页面为准。
    • 数据来自本机真实运行,五种语言的版本写在页脚;耗时对比只用 Python 测量。
    • 没有覆盖:Java、JavaScript 等语言里 split 在结尾空字符串上的各自行为;含制表符、换行的空白。
    京ICP备2026067502号-1京公网安备11010502063487号