给定一个由单词和空格组成的字符串,返回最后一个单词的长度。单词是只含字母、被空格分隔的字符串,并且字符串开头和结尾都可能有多余的空格。最直观的写法是按空格切分再取最后一段,但这里有一个陷阱:结尾有空格时,按单个空格切分会得到一个空字符串。更好的做法是从字符串末尾往回扫:先跳过结尾的空格,再数最后一个单词的字符,遇到空格或者到达开头就停。本文用真实运行展示切分写法的陷阱,实测两种写法在长字符串上的耗时,给出五种语言的实现,并把从右往左的扫描做成分步演示。
完整题目见官方页面(链接在文末)。字符串里至少有一个单词。基准解是 s.split()[-1]:按任意连续空白切分,取最后一段的长度,与从后往前扫描是两种写法。一共 12 组用例,覆盖:官方示例、结尾有空格、开头有空格、首尾都有空格、只有一个单词、单词之间有多个空格:
输入 ["Hello World"] 输出 5 输入 [" fly me to the moon "] 输出 4 输入 ["luffy is still joyboy"] 输出 6 输入 ["a"] 输出 1 输入 ["a "] 输出 1 输入 [" a"] 输出 1
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
$ 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; } }
$ 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 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; }
$ 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; } };
$ 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 的返回值一致。