文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载双指针解法全解925. 长按键入LeetCode Long Pressed Name长按键入是一道经典的字符串双指针问题通过两个指针分别扫描name与typed两个字符串判断键入结果能否由长按产生。本指南将完整复现题目、四个官方示例以及 InterviewGuide 仓库中阿秀记录的 C 解法并补充复杂度分析、边界推演与同题多语言变式帮助你彻底吃透这道 Easy 题。一、题目概述与核心考点1. 题目描述你的朋友正在使用键盘输入他的名字name。偶尔在键入字符c时按键可能会被长按而字符可能被输入1 次或多次。你将会检查键盘输入的字符typed。如果它对应的可能是你的朋友的名字其中一些字符可能被长按那么就返回True。函数签名Cbool isLongPressedName(string name, string typed);2. 四个官方示例示例nametyped输出解释1alexaaleextruealex中的a和e被长按2saeedssaaeddfalsee一定需要被键入两次但typed中e只出现一次3leeleelleeeleetrue长按了l、e4laidenlaidentrue长按名字中的字符并不是必要的3. 核心考点双指针思想本题是双指针遍历双字符串的入门级经典题与验证回文串合并两个有序数组同属一类模板贪心匹配每次只关注当前两个指针指向的字符是否相等能匹配就尽量匹配边界判断typed长度小于name时一定为false遍历结束后必须保证name被完整匹配。二、思路分析如何判断长按是否成立1. 长按的本质长按意味着typed中某个字符c的出现次数可以大于等于name中对应位置字符c的出现次数但顺序不能乱。即typed是name在字符连续分组意义上的一种超序列supersequence。2. 判定规则用指针i扫描name指针j扫描typed若name[i] typed[j]两个指针同时前进若name[i] ! typed[j]只能让j前进跳过typed中多出来的长按字符遍历结束后i必须走到name末尾。⚠️ 这一版解法的关键缺陷在示例 2中暴露当typed中出现name中不存在的字符时如ssaaedd中的d该算法会直接跳过它并误判为true。真正的正确解法需要对字符段进行计数比较下文第四节会给出完整正确版本。三、InterviewGuide 仓库中的 C 解法第一版在 InterviewGuide 仓库中阿秀记录了这一题的第一版解法位于 925.长按键入.md当时实测执行用时 0 ms击败 100.00% 的 cpp 提交内存消耗 8.2 MB击败 99.22% 的用户bool isLongPressedName(string name, string typed) { if (typed.size() name.size()) return false; int lenName name.size(), lenTyped typed.size(); unsigned i 0, j 0; while (i lenName j lenTyped) { if (name[i] typed[j]) { i; j; } else { j; } } if (i lenName j lenTyped) return true; else return false; }代码逐行解析if (typed.size() name.size()) return false;长度剪枝。长按只会让typed更长不可能更短直接排除unsigned i 0, j 0;双指针初始化while (i lenName j lenTyped)任一字符串扫描完即停相等则双指针前进匹配成功不等则只动j跳过长按产生的多余字符最终判断i lenName确保name被完整匹配。复杂度分析时间复杂度O(lenName lenTyped)最坏情况下两个指针各扫描一遍空间复杂度O(1)只使用了常数个变量。该版本的适用边界它能通过示例 1、3、4但会错误通过示例 2saeedvsssaaedd——这正是只比较单字符、不比较字符段的隐患适合作为快速初版理解双指针框架。四、正确解法字符段计数法官方推荐思路1. 核心思想与其逐字符比较不如按连续字符分组把name分成若干字符段如a | l | e | x把typed也分成若干字符段如aa | l | ee | x然后逐段比较段字符必须相同typed中该段长度必须 ≥name中该段长度。2. C 实现bool isLongPressedName(string name, string typed) { int i 0, j 0; int n name.size(), m typed.size(); while (i n j m) { if (name[i] ! typed[j]) return false; // 段首字符必须一致 int cntN 0, cntT 0; char c name[i]; while (i n name[i] c) { i; cntN; } // 统计 name 段长 while (j m typed[j] c) { j; cntT; } // 统计 typed 段长 if (cntT cntN) return false; // typed 段长不足 } // 两个字符串都必须被完整扫描完 return i n j m; }3. 正确性验证对照四个示例示例name 分段typed 分段判定1a(1)/l(1)/e(1)/x(1)aa(2)/l(1)/ee(2)/x(1)每段 2≥1true2s(1)/a(1)/e(2)/d(1)ss(2)/aa(2)/e(1)/d(2)e 段 1 2false✅3l(1)/e(2)/l(1)/e(2)ll(2)/ee(2)/l(1)/e(2)每段满足true4逐段 11逐段 11true4. 为什么第一版会错、这一版才对第一版只做了字符是否相等的判断当typed中混入name完全没有的字符示例 2 的d段其实是d出现 2 次而name中d在e之后顺序上多出的d段被跳过时无法感知多余字符段的存在。字符段计数法通过return i n j m双端校验彻底堵住了这个漏洞。五、同题多语言变式与边界测试1. Python 3 实现class Solution: def isLongPressedName(self, name: str, typed: str) - bool: i j 0 n, m len(name), len(typed) while i n and j m: if name[i] ! typed[j]: return False c name[i] cnt_n cnt_t 0 while i n and name[i] c: i 1 cnt_n 1 while j m and typed[j] c: j 1 cnt_t 1 if cnt_t cnt_n: return False return i n and j m2. Go 实现func isLongPressedName(name string, typed string) bool { i, j : 0, 0 n, m : len(name), len(typed) for i n j m { if name[i] ! typed[j] { return false } c : name[i] cntN, cntT : 0, 0 for i n name[i] c { i cntN } for j m typed[j] c { j cntT } if cntT cntN { return false } } return i n j m }3. 关键边界测试用例测试用例期望输出说明namea, typedatrue无长按也合法namea, typedaatrue单个字符被长按namea, typedbfalse字符不匹配nameab, typedaabtrue首字符长按nameabc, typedaabbcctrue每个字符都被长按nameabc, typedaabbcfalsec段数量不足namealex, typedaaleexafalsetyped末尾多出name中没有的字符段六、扩展练习与进阶思路1. 同类双指针字符串题在 InterviewGuide 仓库的双指针分类下还有一道 Easy 级题目532. 数组中的 K-diff 数对它同样运用了排序 双指针/二分的思路适合与本题对照学习。2. 进阶变式统计长按次数如果题目要求输出每个字符被长按的次数可以维护一个哈希表记录每个字符段的实际次数差值多字符串版本将两个字符串推广为模式串匹配可以联想到正则表达式中的量词语义——本题本质上就是贪心匹配一个c模式的序列与滑动窗口对比本题是双指针同时前进而滑动窗口通常是一个指针先走、另一个指针后追两者定位不同注意区分。七、小结要点结论核心算法双指针 字符段计数时间复杂度O(len(name) len(typed))空间复杂度O(1)易错点只比较单字符会漏判多余字符段必须同时校验i n j m仓库出处docs/notes/03-hunting_job/03-algorithm/03-leetcode/08-️双指针/easy/925.长按键入.md掌握本题后建议继续刷双指针分类下的其余题目将双指针 字符串分段这套组合拳练熟面试中遇到同类字符串匹配问题就能举一反三了。赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐LeetCode 925. Long Pressed Name 长按键入LeetCode-Go 双指针题解与边界分析LeetCode 925. Long Pressed Name 长按键入LeetCode Go 双指针题解与边界分析 导读 本文围绕 LeetCode 第 9示例工程长按键入LeetCode 0925题解基于「算法通关手册」的分离双指针字符串匹配实战解析长按键入LeetCode 0925题解基于「算法通关手册」的分离双指针字符串匹配实战解析 本篇题解围绕 LeetCode 0925「长按键入」展开讲解如教程文档知识库双指针算法实战指南LogicStack-LeetCode 仓库 LeetCode 双指针专题全解析双指针算法实战指南LogicStack LeetCode 仓库 LeetCode 双指针专题全解析 本指南以仓库 Index/双指针.md https://l教程文档上一篇G-Helper华硕笔记本性能调优终极指南下一篇5分钟快速部署Open WebUI打造你的本地AI对话平台终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考