LeetCode 58. 最后一个单词的长度|逆向双指针解法(多语言实现详解)
LeetCode 58. 最后一个单词的长度|逆向双指针解法(多语言实现详解)
本篇技术指南基于 doocs/leetcode 开源仓库中 0058.Length of Last Word 的题解文档展开,系统讲解“最后一个单词的长度”这一经典字符串问题的题目语义、逆向双指针算法推导、复杂度分析,并完整覆盖仓库中 Python、Java、C++、Go、TypeScript、Rust、JavaScript、C#、PHP 共 9 种语言的实现及边界验证。读完本文,你既能独立写出该题的 O(n) 时间、O(1) 空间解法,也能理解同一思路在不同语言下的落地差异。
题目理解:单词由空格界定,目标只有“最后一个”
给你一个字符串
s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。单词是指仅由字母组成、不包含任何空格字符的最大子字符串。
这道题是典型的“字符串 + 模拟”入门题,属于简单难度,标签为字符串。它的核心难点不在算法本身,而在于准确理解“最后一个单词”的边界:字符串末尾可能带有多余空格,因此不能简单认为“最后一个字符之后就是最后一个单词”。
示例与输入约束
仓库文档给出了三个典型示例:
| 输入 | 输出 | 解释 |
|---|---|---|
s = "Hello World" |
5 | 最后一个单词是 "World",长度为 5 |
s = " fly me to the moon " |
4 | 最后一个单词是 "moon",长度为 4(注意尾部有两个空格) |
s = "luffy is still joyboy" |
6 | 最后一个单词是 "joyboy",长度为 6 |
输入约束(见 README.md):
1 <= s.length <= 10^4s仅有英文字母和空格' '组成s中至少存在一个单词
第三条约束非常关键:它保证了“最后一个单词”一定存在,算法无需处理“全空格字符串”的异常分支,只需关注尾部空格与单词左边界的定位。
方法一:逆向遍历 + 双指针
思路推导
文档的思考记录(thinking 注释)给出了清晰的推导过程:
- 若按空格切分(
split)再取末段,在n <= 10^4的规模下可以通过,但会扫完整串并分配若干子串,存在不必要的开销; - 中间的单词完全无需处理,答案只取决于贴在串尾的最后一个单词;
- 最后一个单词的右侧可能还有空格,所以正确的做法是从右向左扫描:
- 先跳过尾部所有空格,找到最后一个单词的最后一个字符,下标记为
i; - 再从
i继续向左,找到第一个空格字符,它恰好是最后一个单词第一个字符的前一个位置,记为j; - 最后一个单词的长度即为
i - j。
- 先跳过尾部所有空格,找到最后一个单词的最后一个字符,下标记为
用指针图可以直观表达(以 " fly me to the moon " 为例):
索引: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
字符: ' ' ' ' ' ' f l y ...
... m o o n ' ' ' '
↑ ↑
j i
长度 = i - j = 17 - 13 = 4
其中 i 指向 n(单词最后一个字符),j 指向 n 前面的空格,二者下标之差正好等于单词长度。
复杂度分析
- 时间复杂度:
O(n),其中n为字符串s的长度。最坏情况下(如字符串只有一个单词且无尾部空格)需要从末尾一路扫到开头,但每个字符至多被访问一次; - 空间复杂度:
O(1),全程只使用两个整数下标,不产生任何子串分配。
这正是该方法相比 split 方案的核心优势:不修改字符串、不分配子串、至多扫描一次。
多语言实现:仓库源码全解析
以下实现与仓库中的 Solution 源码目录 一一对应,读者可以直接对照文件阅读。
Python3
对应文件:Solution.py
class Solution:
def lengthOfLastWord(self, s: str) -> int:
i = len(s) - 1
while i >= 0 and s[i] == ' ':
i -= 1
j = i
while j >= 0 and s[j] != ' ':
j -= 1
return i - j
Python 中字符串索引从 0 开始,len(s) - 1 是末位下标;两个 while 循环分别负责“跳过尾部空格”和“越过单词字符”,循环条件中的 i >= 0 与 j >= 0 保证了下标不越界。
Java
对应文件:Solution.java
class Solution {
public int lengthOfLastWord(String s) {
int i = s.length() - 1;
while (i >= 0 && s.charAt(i) == ' ') {
--i;
}
int j = i;
while (j >= 0 && s.charAt(j) != ' ') {
--j;
}
return i - j;
}
}
Java 通过 charAt(i) 按下标取字符,其余逻辑与 Python 完全同构。
C++
对应文件:Solution.cpp
class Solution {
public:
int lengthOfLastWord(string s) {
int i = s.size() - 1;
while (~i && s[i] == ' ') {
--i;
}
int j = i;
while (~j && s[j] != ' ') {
--j;
}
return i - j;
}
};
C++ 版本用 ~i 代替 i >= 0 作为循环条件,这是一个值得注意的细节:-1 的二进制补码全为 1,按位取反后为 0,因此 ~(-1) == 0,~i 等价于 i != -1,即 i >= 0,写法更简洁。
Go
对应文件:Solution.go
func lengthOfLastWord(s string) int {
i := len(s) - 1
for i >= 0 && s[i] == ' ' {
i--
}
j := i
for j >= 0 && s[j] != ' ' {
j--
}
return i - j
}
Go 中 s[i] 返回 byte(uint8),与空格字面量 ' ' 比较即可;若输入含多字节字符需要改用 rune 遍历,但本题约束“仅有英文字母和空格”保证了字节索引与字符索引一致。
TypeScript
对应文件:Solution.ts
function lengthOfLastWord(s: string): number {
let i = s.length - 1;
while (i >= 0 && s[i] === ' ') {
--i;
}
let j = i;
while (j >= 0 && s[j] !== ' ') {
--j;
}
return i - j;
}
TypeScript 与 JavaScript 采用同一套双指针写法,使用严格相等 === / !== 比较。
JavaScript
对应文件:Solution.js
/**
* @param {string} s
* @return {number}
*/
var lengthOfLastWord = function (s) {
let i = s.length - 1;
while (i >= 0 && s[i] === ' ') {
--i;
}
let j = i;
while (j >= 0 && s[j] !== ' ') {
--j;
}
return i - j;
};
C#
对应文件:Solution.cs
public class Solution {
public int LengthOfLastWord(string s) {
int i = s.Length - 1;
while (i >= 0 && s[i] == ' ') {
--i;
}
int j = i;
while (j >= 0 && s[j] != ' ') {
--j;
}
return i - j;
}
}
C# 与 Java 语法接近,方法名采用 PascalCase 的 LengthOfLastWord。
Rust:trim_end + 反向迭代的变体
对应文件:Solution.rs
impl Solution {
pub fn length_of_last_word(s: String) -> i32 {
let s = s.trim_end();
let n = s.len();
for (i, c) in s.char_indices().rev() {
if c == ' ' {
return (n - i - 1) as i32;
}
}
n as i32
}
}
Rust 版本采用了略有不同的实现策略:
trim_end()先去除尾部空格,天然消解“尾部空格干扰”;char_indices().rev()从后向前按字符迭代,同时得到下标i与字符c;- 遇到空格即说明该空格之后、原串末尾之间全是最后一个单词,返回
n - i - 1; - 若整个去尾串没有任何空格(只有一个单词),返回
n。
注意 char_indices() 处理的是字符边界而非字节偏移,能正确兼容多字节 UTF-8 字符。
PHP:逐字符弹出的另类实现
对应文件:Solution.php
class Solution {
/**
* @param String $s
* @return Integer
*/
function lengthOfLastWord($s) {
$count = 0;
while ($s[strlen($s) - 1] == ' ') {
$s = substr($s, 0, -1);
}
while (strlen($s) != 0 && $s[strlen($s) - 1] != ' ') {
$count++;
$s = substr($s, 0, -1);
}
return $count;
}
}
PHP 版不用下标做差,而是“逐字符从尾部弹出”:第一个循环弹出所有尾部空格,第二个循环逐个弹出单词字符并计数。思路与双指针完全等价,只是以“修改字符串”换取了“免去下标管理”。虽然每次 substr 都产生新串,但由于 n <= 10^4,实际开销仍在可接受范围内,且代码可读性很高。
边界情况与实测验证
为验证算法在边界输入下的行为,这里使用仓库中的 Python 与 JavaScript 实现做了一组实测(结果与文档示例一致):
| 输入 | 输出 | 说明 |
|---|---|---|
"Hello World" |
5 | 文档示例 1 |
" fly me to the moon " |
4 | 文档示例 2,含前导与尾部空格 |
"luffy is still joyboy" |
6 | 文档示例 3 |
"a" |
1 | 单字符单词、无空格 |
"a " |
1 | 单词后紧跟尾部空格,需先跳过 |
值得关注的边界场景:
- 尾部多空格:如
"moon ",第一步跳过空格后i才指向n,若跳过split思路容易出错; - 单单词无空格:
"a"时第一轮循环不执行,第二轮从i = 0走到j = -1,结果0 - (-1) = 1,正确; - 全空格字符串:超出题目约束(保证至少一个单词),但算法会返回 0,可作为防御性理解的参考。
解法对比与扩展思考
| 方案 | 思路 | 时间 | 空间 | 说明 |
|---|---|---|---|---|
split 后取末段 |
正向切分 | O(n) | O(n) | 实现最简单,但分配子串、扫描整串 |
| 逆向遍历 + 双指针(本文方法) | 反向扫描 | O(n) | O(1) | 只扫必要字符,不分配子串,仓库默认解法 |
语言内置 API(如 trim_end + rfind) |
反向查找 | O(n) | O(1) | Rust 版本即为其变体 |
什么时候用哪种? 在真实业务中,如果字符串规模极大(如超长日志行),应优先 O(1) 空间的逆向扫描;如果追求代码可读性且规模可控,split 方案同样成立。仓库文档在思考注释中明确给出了取舍依据:n <= 10^4 时 split 可行,但“中间的单词无需处理”意味着更优解是从右向左只处理必要部分——这正是工程上“按需计算”思维的体现。
仓库资源索引
- 题目与题解文档(中英双语):README.md / README_EN.md
- 多语言实现源码:
Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.js、Solution.cs、Solution.rs、Solution.php,均位于 0058.Length of Last Word 目录 下 - 更多题目可按编号在仓库 solution 目录下检索,完整题单见 solution/README.md