教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇题解围绕 LeetCode 0925「长按键入」展开讲解如何用分离双指针在typed字符串中匹配存在重复长按字符的name字符串。文中不仅给出可直接运行的完整 Python 实现与逐行分析还结合「算法通关手册」仓库中双指针基础教程里「分离双指针」的通用模板与求解步骤从方法论层面讲透这道题帮助你掌握一类双序列同步比较的字符串匹配套路。题目概述题目编号0925. 长按键入标签双指针、字符串难度简单关联题解文档docs/solutions/0900-0999/long-pressed-name.md题目大意你的朋友正在使用键盘输入他的名字name。偶尔在键入字符时按键可能会被长按导致某个字符被输入 1 次或多次。现在给定代表名字的字符串name以及实际输入的字符串typed要求检查键盘输入的字符typed是否可能是朋友的名字其中一些字符可能被长按。如果可能返回True否则返回False。数据说明$1 \le name.length,\ typed.length \le 1000$name和typed的字符都是小写字母示例示例 1输入name alex, typed aaleex 输出true 解释alex 中的 a 和 e 被长按。示例 2输入name saeed, typed ssaaedd 输出false 解释e 一定需要被键入两次但在 typed 的输出中不是这样。思路 1分离双指针核心思想这道题的本质是在typed中按顺序匹配name同时允许typed中出现字符的重复长按但不允许出现多余字符或顺序错乱。题目属于两个不同字符串、两指针独立移动的比较问题恰好对应双指针基础教程中定义的分离双指针分别在两个不同序列上各设置一个指针两个指针独立地在各自序列中移动协同完成特定任务。在仓库的分类清单 00_06_categories_list.md 中本题被明确归入「分离双指针题目」一类与「两个数组的交集 II」「比较含退格的字符串」「判断子序列」等题目并列。通用模板对照双指针基础教程中给出的分离双指针通用模板如下# 初始化两个指针分别指向两个数组的起始位置 left_1, left_2 0, 0 # 当两个指针都未遍历到各自数组末尾时循环进行比较 while left_1 len(nums1) and left_2 len(nums2): if 满足条件 1: # 通常表示两个指针指向的元素相等 # 此时可以将该元素加入结果集如交集并同时移动两个指针 left_1 1 left_2 1 elif 满足条件 2: # 通常表示第一个数组当前元素较小 # 只移动第一个指针继续比较下一个元素 left_1 1 elif 满足条件 3: # 通常表示第二个数组当前元素较小 # 只移动第二个指针继续比较下一个元素 left_2 1本题在模板基础上做了适配left_1指向nameleft_2指向typed当两字符相等时同时右移当不相等时判断是否为typed中允许的长按重复从而只移动left_2。求解步骤使用两个指针left_1、left_2left_1指向字符串name的起始位置left_2指向字符串typed的起始位置。如果name[left_1] typed[left_2]说明当前字符匹配将left_1、left_2同时右移。如果name[left_1] ! typed[left_2]则分两种情况判断若typed[left_2]与前一个位置元素typed[left_2 - 1]相等说明typed中出现了长按产生的重复元素将left_2右移过滤掉这个重复字符若typed[left_2]与前一个位置元素typed[left_2 - 1]不相等说明typed中出现了多余元素与name无法匹配直接返回False。当left_1 len(name)或left_2 len(typed)时跳出主循环。随后过滤掉typed末尾可能存在的重复元素长按余量。最后判断如果left_1 len(name)且left_2 len(typed)说明name全部匹配且typed恰好被消费完毕返回True否则返回False。代码实现class Solution: def isLongPressedName(self, name: str, typed: str) - bool: left_1, left_2 0, 0 while left_1 len(name) and left_2 len(typed): if name[left_1] typed[left_2]: left_1 1 left_2 1 elif left_2 0 and typed[left_2 - 1] typed[left_2]: left_2 1 else: return False while 0 left_2 len(typed) and typed[left_2] typed[left_2 - 1]: left_2 1 if left_1 len(name) and left_2 len(typed): return True else: return False代码逐段解读第一阶段主循环同步匹配while left_1 len(name) and left_2 len(typed): if name[left_1] typed[left_2]: left_1 1 left_2 1当两个指针都未越界时进入循环。若当前name字符与typed字符相等说明typed中该字符可以认领name中的一次出现两指针同步前进。elif left_2 0 and typed[left_2 - 1] typed[left_2]: left_2 1当字符不等时先判断typed[left_2]是否是长按的延续与前一个字符相同。注意这里通过left_2 0防止在typed起始位置访问typed[-1]。如果是延续说明这只是多余的一次重复按键只移动left_2跳过它。else: return False如果字符不等、且不是重复延续说明typed中出现了name里根本没有的多余字符或者顺序错乱直接判定不匹配。第二阶段清理尾部重复while 0 left_2 len(typed) and typed[left_2] typed[left_2 - 1]: left_2 1主循环可能在left_1 len(name)时提前退出即name已全部匹配但typed还有剩余。此时剩余字符必须全部是name最后一个字符的长按重复才能算合法因此用这个循环过滤尾部连续重复字符。第三阶段终态判定if left_1 len(name) and left_2 len(typed): return True else: return False只有name被完整匹配、且typed也被完整消费无多余字符残留时才返回True。示例推演示例 1name alextyped aaleex步骤left_1left_2比较动作100name[0]avstyped[0]a相等双指针右移211name[1]lvstyped[1]a不等且typed[0]atyped[1]a长按重复left_2右移312name[1]lvstyped[2]l相等双指针右移423name[2]evstyped[3]e相等双指针右移534name[3]xvstyped[4]e不等且typed[3]etyped[4]e长按重复left_2右移635name[3]xvstyped[5]x相等双指针右移主循环结束时left_1 4 len(name)left_2 6 len(typed)尾部清理循环不触发最终返回True。这与题目解释一致a和e被长按。示例 2name saeedtyped ssaaedd步骤left_1left_2比较动作100svss相等双指针右移211avss不等typed[0]styped[1]s长按重复left_2右移312avsa相等双指针右移423evsa不等typed[2]atyped[3]a长按重复left_2右移524evse相等双指针右移635evsd不等typed[4]e ! typed[5]d多余字符返回Falsename中的第二个e一定需要被键入两次name saee d但typed中e只出现了一次随后直接出现了d因此返回False与题目解释吻合。边界情况与易错点typed起始位置重复判断left_2 0的判空条件必不可少否则当left_2 0且字符不等时访问typed[-1]会取到字符串末尾字符产生错误逻辑Python 负索引不会报错但语义错误。name匹配完但typed有剩余必须通过尾部清理循环判断剩余字符是否全部为最后一个字符的长按重复。例如name alextyped alexxxxx主循环在left_1 4时退出尾部循环会依次跳过 4 个x最终判定合法。typed中字符缺失例如name alextyped alx主循环中name[1]e永远无法与typed中后续字符匹配最终left_1无法到达len(name)返回False。typed出现name没有的字符例如name alextyped alebx当left_1指向e、left_2指向b时b既不是匹配字符也不是重复延续直接返回False。长度关系约束由于name中每个字符在typed中至少出现一次隐含 $len(typed) \ge len(name)$若typed比name短必然无法匹配本算法会自然地在循环退出后返回False。复杂度分析时间复杂度$O(n m)$。其中 $n$、$m$ 分别为字符串name、typed的长度。两个指针分别只会单调右移name指针最多移动 $n$ 次typed指针最多移动 $m$ 次整体为线性时间。空间复杂度$O(1)$。只使用了两个指针变量没有借助额外的数据结构。从源码结构看分离双指针的应用家族本题的解法思路在仓库中并非孤例。根据分类清单 00_06_categories_list.md分离双指针适用于双序列按序协同比较的问题仓库中同类的题解还包括0349. 两个数组的交集两有序数组指针同步比较收集交集元素0350. 两个数组的交集 II同样的双序列同步比较处理重复元素计数0844. 比较含退格的字符串双指针从尾部同步回溯比较0392. 判断子序列双序列匹配判断s是否为t的子序列与本题的顺序匹配 容忍重复逻辑高度相似。对比可见长按键入与判断子序列都属于一个字符串是否能在另一个字符串中按顺序匹配出来的问题区别在于本题额外允许匹配过程中跳过typed中与前一字符相同的重复字符长按。掌握这种相等则同进、不等则按规则单进的指针推进策略即可举一反三。总结LeetCode 0925「长按键入」是一道典型的分离双指针入门题核心要点有三双序列独立指针left_1匹配nameleft_2扫描typed各自只前进不后退长按规则建模typed中的字符要么与name当前字符匹配双指针同进要么与自身前一字符重复仅typed指针前进否则直接判定失败收尾判定严谨name必须被完整匹配且typed剩余部分只能是尾部重复二者缺一不可。通过本题你可以掌握分离双指针在字符串匹配场景下的标准套路。更多双指针方法论对撞指针、快慢指针、分离双指针的求解步骤与通用模板可继续阅读双指针基础教程并通过0900-0999 题解索引查阅其他字符串双指针题目的完整解析。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0541 反转字符串 II——双指针分段反转的完整解法剖析AlgoNote 算法通关手册LeetCode 0541 反转字符串 II——双指针分段反转的完整解法剖析 本篇技术指南围绕 AlgoNote「算法通关手册教程文档知识库删列造序LeetCode 0944题解AlgoNote 算法通关手册中的数组与字符串双指针模拟实战删列造序LeetCode 0944题解AlgoNote 算法通关手册中的数组与字符串双指针模拟实战 本篇题解来自「算法通关手册」AlgoNote项目教程文档知识库AlgoNote 算法通关手册KMP 字符串匹配算法详解与 Python 实战AlgoNote 算法通关手册KMP 字符串匹配算法详解与 Python 实战 本文是「算法通关手册」字符串专题的核心篇章系统讲解 KMPKnuth Mo教程文档知识库上一篇PromptWizard可解释性研究如何可视化提示词优化的决策过程下一篇MHVideoPhotoGallery多语言支持为全球用户提供本地化体验创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
