LeetCode 925. 长按键入
目录
题目描述
题意分析
你的朋友在键盘上输入
name，但某些按键可能被长按了，导致对应字符在结果里连续重复多次。给出实际打出来的字符串typed，判断它是否可能由输入name时长按产生。「长按」这个动作的语义要抠准：它只能让某个字符重复更多次，不能凭空插入别的字符，也不能漏掉任何字符，更不能改变顺序。所以
typed必须能被切成若干连续段，每段字符与name的对应字符相同，且每段长度大于等于name中该字符的连续次数。注意长按次数可以是 0 次额外重复——也就是
typed与name完全相同时答案为真。题目问的是「可能」，不要求真的发生过长按。约束里两串长度都在 1 到 1000 之间，全是小写字母。规模极小，$O(m + n)$ 一遍扫描足够。这题的分数全在边界与终止条件上，不在效率。
边界要盯住三处：
typed比name短时必然为假；typed扫完但name还有剩余字符时也为假（比如name = "alex"、typed = "ale"）；typed结尾多出一段合法长按（比如typed = "alexx"）时为真。第二处最容易漏，它决定了循环退出后还得再判一次。
解法：双指针扫描
核心思路
一种直觉做法是把两个串都压缩成「字符 + 连续次数」的分组形式，再逐组比较：字符必须相同，且
typed的次数不小于name的次数，组数也必须一致。这个做法完全正确、可读性也好，但要额外开两个 $O(n)$ 的列表来存分组结果。瓶颈在于我们把「分组」和「比较」拆成了两个阶段。而分组信息其实可以边扫边用——判断某个字符是不是长按产生的，只需要看它与前一个字符是否相同，不必真的统计次数。
于是用双指针：
i指向name中待匹配的字符，j扫描typed。每一步只有三种情况，且是互斥有序的。第一，
name[i] == typed[j]：这是一次正常匹配，两个指针同时前进。这一支必须优先判断——只要能正常匹配就正常匹配，把「算作长按」留给匹配不上的时候，否则会出现该推进i却没推进的错配。第二，匹配不上，但
typed[j] == typed[j-1]：说明当前字符是前一个字符的重复，即长按产生的多余字符，只推进j，i原地不动。第三，两者都不成立：
typed[j]既不是name需要的字符，也不是上一个字符的延续，它是凭空多出来的，直接返回假。不变量：每轮循环开始时，
typed的前j个字符恰好可以由name的前i个字符经过若干次长按生成，且这个i是所有可行方案里唯一的取值（贪心匹配不会错过更优解——因为字符相同时立即匹配总不劣，留着不匹配只会让后续更难）。循环以
j走完typed为终止条件。退出时typed全部解释完毕，但name未必用完，所以最后必须再判一次i == name.length()。这一句是全题的收口：它把「typed太短、没能覆盖name的全部字符」这一类错误挡在门外。
解题步骤
- 初始化
i = 0、j = 0：两个指针都从头开始，分别追踪「name已匹配到哪」和「typed已解释到哪」。- 循环条件用
j < typed.length()：以typed为主导，因为每个typed字符都必须被解释成「正常匹配」或「长按重复」二者之一，一个都不能剩。若改用i < name.length()作条件，typed尾部多出的非法字符（如name = "a"、typed = "ab"）就检查不到。- 优先分支：
i < name.length() && name.charAt(i) == typed.charAt(j)：i < name.length()的越界保护必须写在前面并用短路与，否则name用完后charAt(i)会直接抛异常。命中则i++、j++。- 次选分支：
j > 0 && typed.charAt(j) == typed.charAt(j - 1)：j > 0保护了j - 1不越界；j = 0时若第一个字符就匹配不上，本来也该判假。命中则只j++，i不动——长按不消耗name的字符。- 两分支都不成立返回 false：这个字符无法解释，立刻否定，不必继续。
- 循环外返回
i == name.length()：不能直接return true。typed解释完了不等于name匹配完了。以
name = "alex"、typed = "aaleex"走一遍，正确答案是 true。初始
i = 0、j = 0。第 1 步：
name[0] = 'a'与typed[0] = 'a'相同，正常匹配，i = 1、j = 1。第 2 步：
name[1] = 'l'与typed[1] = 'a'不同；typed[1] = 'a'与typed[0] = 'a'相同，判定为长按，只推进j = 2。这里i保持在 1，意味着字母l还等着被匹配。第 3 步：
name[1] = 'l'与typed[2] = 'l'相同，正常匹配，i = 2、j = 3。第 4 步：
name[2] = 'e'与typed[3] = 'e'相同，i = 3、j = 4。第 5 步：
name[3] = 'x'与typed[4] = 'e'不同；typed[4] = 'e'与typed[3] = 'e'相同，长按，j = 5。第 6 步：
name[3] = 'x'与typed[5] = 'x'相同，i = 4、j = 6。
j = 6等于typed长度，循环退出。i = 4等于name长度，返回 true。再看一个假的用例
name = "saeed"、typed = "ssaaedd"。前面几步依次是：s匹配（i=1,j=1）、typed[1]='s'长按（j=2）、a匹配（i=2,j=3）、typed[3]='a'长按（j=4）、e匹配（i=3,j=5）。第 6 步时name[3] = 'e'与typed[5] = 'd'不同，且typed[5] = 'd'与typed[4] = 'e'也不同——这个d无法解释成长按，返回 false。正确，因为name里e出现了两次而typed里只打出一次。最后看收口那一句的必要性：
name = "alex"、typed = "ale"。三步正常匹配后i = 3、j = 3，循环退出。若直接return true会答错；判i == 4不成立，正确返回 false。
代码实现
class Solution {
public boolean isLongPressedName(String name, String typed) {
int i = 0;
int j = 0;
while (j < typed.length()) {
if (i < name.length() && name.charAt(i) == typed.charAt(j)) {
i++;
j++;
} else if (j > 0 && typed.charAt(j) == typed.charAt(j - 1)) {
j++;
} else {
return false;
}
}
return i == name.length();
}
}
func isLongPressedName(name string, typed string) bool {
i, j := 0, 0
for j < len(typed) {
if i < len(name) && name[i] == typed[j] {
i++
j++
} else if j > 0 && typed[j] == typed[j-1] {
j++
} else {
return false
}
}
return i == len(name)
}
复杂度分析
- 时间复杂度：$O(m + n)$，
m为name长度、n为typed长度。i与j都只增不减，每轮循环至少推进j一格，全程不回退。- 空间复杂度：$O(1)$。只用了两个下标，判定长按靠比较
typed[j]与typed[j-1]，不需要预先分组或统计次数。
关键点总结
- 「A 能否由 B 经过某种单调变换得到」这类题，几乎都能用双指针一趟扫完：一个指针追踪源串的匹配进度，另一个负责解释目标串的每个字符。
- 三个分支的优先级决定正确性：能正常匹配就优先匹配，匹配不上才考虑长按，都不行才否定。顺序一换就会出现该推进
i时没推进的错配。- 判断长按不需要统计连续次数，只看「与前一个字符是否相同」即可——把分组信息即用即弃，省掉一趟预处理和 $O(n)$ 空间。
- 循环以
typed为主导（每个字符都必须被解释），退出后再单独校验name是否用完；两个串的结束条件必须分开处理，这是本题最主要的失分点。- 越界保护要写在短路与的左侧：
i < name.length() && ...和j > 0 && ...，顺序写反会在name提前用完或j = 0时直接崩溃。- 面试视角：写完立刻用
"alex"/"ale"（name没用完）、"a"/"ab"（typed有非法尾巴）、"alex"/"alex"（零次长按）三个用例口述验证，比讲复杂度更能体现边界意识。
易错点总结
- 循环结束后直接
return true：name = "alex"、typed = "ale"会返回 true，正确答案是 false——name里的x根本没被打出来。- 循环条件写成
i < name.length()：name = "a"、typed = "ab"中i走完就退出，尾部非法的b从未被检查，误返回 true。- 两个分支的判断顺序颠倒：先判
typed[j] == typed[j-1]再判正常匹配，name = "aa"、typed = "aa"中第二个a会被当成长按而不推进i，最终i = 1 != 2，误返回 false。i < name.length()的保护漏写或写在右侧：name = "a"、typed = "aa"中i变成 1 后再执行name.charAt(1)，抛出下标越界异常。j > 0的保护漏写：name = "b"、typed = "a"中j = 0时访问typed.charAt(-1)，直接异常；正确行为是返回 false。- 长按分支里顺手
i++：name = "alex"、typed = "aaleex"中第 2 步会把i推到 2，字母l被跳过，后续匹配全部错位，误返回 false。- 拿
typed[j]与name[i-1]比较来判长按：name = "ab"、typed = "abb"侥幸正确，但name = "ab"、typed = "aab"中第 2 步typed[1]='a'与name[0]='a'相同也会被判为长按（结果碰巧对），一旦name中出现"aba"这类模式就会误判；判定长按的依据应当是typed内部的连续性。- 先比较长度，
typed.length() < name.length()时提前返回 false 却漏掉其余检查：这一步本身没错（长按只会变长），但若把它当作充分条件写成「长度够就返回 true」，name = "ab"、typed = "cd"会误判为真。- 用「
name是typed的子序列」来判定：name = "ab"、typed = "acb"中ab确实是子序列，但多出的c不是长按产生的，正确答案是 false。子序列条件太松。- 用「排序后相等」或「字符计数相同」判定：长按会改变字符出现次数，
name = "alex"、typed = "aaleex"的计数并不相同，这类做法从根上就不成立。- 误以为
typed必须严格长于name：题目问的是「可能」，零次长按也合法，name = "alex"、typed = "alex"应返回 true。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 392. 判断子序列 | 简单 | 允许任意跳过而非仅重复，条件比本题松，只需单向推进不必判非法字符 |
| 844. 比较含退格的字符串 | 简单 | 双串双指针但要从右往左扫，因为退格的作用方向朝左 |
| 28. 找出字符串中第一个匹配项的下标 | 简单 | 要求连续完全匹配，失配后主串指针需回退或用 KMP 的 next 数组 |
| 443. 压缩字符串 | 中等 | 同样按「连续相同字符」分段，但要把段长回写进原数组 |
| 27. 移除元素 | 简单 | 快慢指针的最简形态，写指针只在保留元素时推进，可与本题的 i 类比 |