题目描述
思路解析
一句话答案：LeetCode 524 通过删除字母匹配到字典里最长单词：对字典每个词用双指针判它是不是 s 的子序列，在是子序列的词里挑最长、同长取字典序小，时间 O(d·n)。
从 s 删掉几个字母，够到字典里哪个词
给一个字符串 s 和一串候选词 dictionary，问：把 s 里某些字母删掉、剩下的保持原来的先后顺序，能拼出字典里哪个词，要最长的那个；多个一样长就取字典序最小的，都够不到就返回空串。题面例子 s="abpcplea"、dictionary=["ale","apple","monkey","plea"]，答案 "apple"。
把 s 所有删法都列出来，为什么行不通
很自然会想到把 s 的所有删法穷举出来：s 长 n，每个字母删或不删两种选择，共 2^n 种结果，n 到 20 就是一百多万条，再和字典比对撑不住。换个方向：不列 s 能变成什么，而是拿字典每个词，直接问它能不能由 s 删字母得到。
「删字母能得到 word」翻成一句什么话
把 s 删几个字母得到 word，等价于说 word 是 s 的子序列——word 的每个字母都能在 s 里按先后顺序对上，中间隔多远都行，但次序不能乱。判子序列有个标准双指针写法：i 指 word 当前要找的字母、j 从头扫 s，s[j] 和 word[i] 相等就算对上一个、i 往后挪一位，不管相不相等 j 每轮都右移。等 i 走到 word 末尾，说明每个字母都按顺序找齐，word 就是子序列。
方向别弄反：i 走候选词 word、j 走源串 s，因为是从 s 里删字母得到 word；也只在相等时推进 i，光看字母都在 s 里出现过不够，次序乱了照样删不出来。
一个词判完是子序列，接下来比什么
判定只解决单个词，外面还要挑答案。遍历字典每个候选，判是不是子序列；是的话再和手里存的最优比：更长就替换，一样长就比字典序、更小才替换。全部试完，手里剩的就是最长且字典序最小的。别碰到第一个子序列就返回——后面可能有更长的，或同样长却更靠前的。
abpcplea 配四个候选，apple 怎么胜出
ale：找 a，第 0 位对上、i 到 1；找 l 跳过 b、p、c、p，第 5 位对上、i 到 2；找 e，第 6 位对上、i 到 3 走完，是子序列，比空答案长，先存 ale。
apple：a 对上第 0 位，p 跳过 b 对上第 2 位，第二个 p 跳过 c 对上第 4 位，l 对上第 5 位，e 对上第 6 位，i 走完 5 个字母，是子序列且比 ale 长，答案换 apple。monkey：首字母 m 扫遍 s 都没有，i 卡在 0，淘汰。
plea：p 跳过 a、b 对上第 2 位，l 对第 5 位，e 对第 6 位，a 对第 7 位，i 走完 4 个字母，也是子序列——但只有 4 个，没比存着的 apple（5 个）长，答案不变。四个试完，apple 胜出。
全军覆没、同长打平，这些角落别漏
复杂度上，设 s 长 n、字典 d 个词，每个候选双指针扫一遍 s 是 O(n)，合计 O(d·n)；只用两个指针加一个答案串，额外空间 O(1)。
几个角落容易漏。没有一个词是子序列时，答案是初始空串，记得给初值。两个候选一样长又都合格，得按字典序取小，返回先遇到的会错。比 s 还长的候选，i 走不到末尾，自然判成非子序列，不必先比长度。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住口诀:内层双指针判子序列,外层比长度、平局比字典序。下面每帧都在套它。
上面这排是源串 s 的每个字母。我们要逐个拿字典里的候选词,放进来用双指针扫 s,看它能不能整词对上。绿色代表对上的字母,蓝色代表扫过但没用上的。
轮到字典第 1 个候选 ale（长度 3）。两个指针都从头开始:i 指它的第一个字母 a,j 从 s 的第 0 位往右扫,去把这些字母依次找出来。
s 第 0 位是 a,正好等于 ale 当前要找的 a,命中!这一格变绿,i 前进到 1。下一个要找 l。
s 第 1 位是 b,不等于现在要找的 l,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 1。
s 第 2 位是 p,不等于现在要找的 l,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 1。
s 第 3 位是 c,不等于现在要找的 l,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 1。
s 第 4 位是 p,不等于现在要找的 l,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 1。
s 第 5 位是 l,正好等于 ale 当前要找的 l,命中!这一格变绿,i 前进到 2。下一个要找 e。
s 第 6 位是 e,正好等于 ale 当前要找的 e,命中!这一格变绿,i 前进到 3。ale 的字母全部对上了。
ale 是子序列,而且比之前的最优更长（或同长更靠前）,刷新最优 = ale。
轮到字典第 2 个候选 apple（长度 5）。两个指针都从头开始:i 指它的第一个字母 a,j 从 s 的第 0 位往右扫,去把这些字母依次找出来。
s 第 0 位是 a,正好等于 apple 当前要找的 a,命中!这一格变绿,i 前进到 1。下一个要找 p。
s 第 1 位是 b,不等于现在要找的 p,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 1。
s 第 2 位是 p,正好等于 apple 当前要找的 p,命中!这一格变绿,i 前进到 2。下一个要找 p。
s 第 3 位是 c,不等于现在要找的 p,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 2。
s 第 4 位是 p,正好等于 apple 当前要找的 p,命中!这一格变绿,i 前进到 3。下一个要找 l。
s 第 5 位是 l,正好等于 apple 当前要找的 l,命中!这一格变绿,i 前进到 4。下一个要找 e。
s 第 6 位是 e,正好等于 apple 当前要找的 e,命中!这一格变绿,i 前进到 5。apple 的字母全部对上了。
apple 是子序列,而且比之前的最优更长（或同长更靠前）,刷新最优 = apple。
轮到候选 monkey,它要找的第一个字母是 m。可整条 s 从头扫到尾,a、b、p、c、p、l、e、a 里没有一个 m,i 一直卡在 0。
monkey 的第一个字母都凑不齐,自然不是子序列,淘汰。最优依旧是 apple。
轮到字典第 4 个候选 plea（长度 4）。两个指针都从头开始:i 指它的第一个字母 p,j 从 s 的第 0 位往右扫,去把这些字母依次找出来。
s 第 0 位是 a,不等于现在要找的 p,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 0。
s 第 1 位是 b,不等于现在要找的 p,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 0。
s 第 2 位是 p,正好等于 plea 当前要找的 p,命中!这一格变绿,i 前进到 1。下一个要找 l。
s 第 3 位是 c,不等于现在要找的 l,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 1。
s 第 4 位是 p,不等于现在要找的 l,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 1。
s 第 5 位是 l,正好等于 plea 当前要找的 l,命中!这一格变绿,i 前进到 2。下一个要找 e。
s 第 6 位是 e,正好等于 plea 当前要找的 e,命中!这一格变绿,i 前进到 3。下一个要找 a。
s 第 7 位是 a,正好等于 plea 当前要找的 a,命中!这一格变绿,i 前进到 4。plea 的字母全部对上了。
plea 是子序列,但它没有比当前最优 apple 更长、平局也没更靠前,最优不变。
四个候选都试完。ale 是子序列但只有 3 个字母,apple 是子序列有 5 个,monkey 淘汰,plea 是子序列但只有 4 个。最长的就是 apple,绿色高亮的就是它在 s 里对上的那 5 个字母。答案 apple。
边界先想清:全军覆没返回空串、同长比字典序、超长候选自然出局。
面试重点:子序列判定 + 多次查询用位置索引加二分。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def findLongestWord(self, s: str, dictionary: List[str]) -> str: def check(s: str, t: str) -> bool: m, n = len(s), len(t) i = j = 0 while i < m and j < n: if s[i] == t[j]: i += 1 j += 1 return i == m ans = "" for t in dictionary: if check(t, s) and (len(ans) < len(t) or (len(ans) == len(t) and ans > t)): ans = t return ans复杂度
- 时间：O(d · n)，d 个候选,每个用双指针扫一遍长 n 的 s
- 空间：O(1)，只用两个指针 + 一个答案串,不开额外结构
易错点
面试追问把动画讲成自己的话
追问如果字典很大、要反复对很多个候选查询,怎么优化单次子序列判定?
追问这题和「判断子序列」那道有什么关系?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
数组中的 k-diff 数对
LeetCode 532 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题