题目描述
思路解析动画文字版
记住口诀:内层双指针判子序列,外层比长度、平局比字典序。下面每帧都在套它。
上面这排是源串 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题