尧图网站建设 
LeetCode 925. Long Pressed Name 长按键入LeetCode-Go 双指针题解与边界分析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 925 题 Long Pressed Name长按键入展开以 LeetCode-Go 仓库中 0925.Long-Pressed-Name 目录 下的官方题解为主体讲解如何用双指针滑动窗口判断长按键盘产生的输入是否可能由给定的名字打出。读完本文你将掌握该题的完整解题思路、Go 源码逐行实现、易错边界用例的判定规则以及如何在本仓库中直接运行测试验证结论。题目描述与约束题目原文摘自 README.mdYour friend is typing his name into a keyboard. Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times. You examine the typed characters of the keyboard. Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.翻译过来就是你的朋友正在用键盘输入自己的名字。有时在输入某个字符 c 时按键可能被长按导致该字符被重复输入 1 次或多次。现在给你观察到的实际键入结果typed判断它是否可能是朋友的名字name经过若干字符也可能没有字符长按后产生的。题目的约束条件如下name.length 1000typed.length 1000name和typed中的字符均为小写字母由于数据规模只有 1000本题对算法复杂度的要求并不苛刻但核心难点在于正确理解长按的语义并处理各种边界情况。题目大意中文解读给定 2 个字符串后者的字符串中包含前者的字符串。比如在打字的过程中某个字符会多按了几下。判断后者字符串是不是比前者字符串存在这样的长按键盘的情况。更严谨地说typed可以看成是name中每个字符的分组被展开的结果——name中每个字符在typed中出现的次数必须不小于 1等于 1 表示没有长按大于 1 表示长按了且字符出现的相对顺序不能改变。因此typed中不允许出现name中没有的字符typed中同一字符组的长度不能少于name中对应字符在原始串中的计数。解题思路双指针滑动窗口扫描README 中明确指出这一题可以借助滑动窗口的思想2 个字符串一起比较如果遇到有相同的字符串窗口继续往后滑动直到遇到了第一个不同的字符如果遇到两个字符串不相等的情况可以直接返回 false。具体到实现上我们维护两个指针指针i指向name中当前正在匹配的字符指针j指向typed中当前正在匹配的字符。算法流程如下字符对齐比较name[i]与typed[j]。如果两者不同说明typed中出现了name中不存在的字符或顺序错乱直接返回false。吃掉相同字符在name和typed都未越界的前提下只要name[i] typed[j]就让i和j同步前进直到遇到第一个不相同的字符。这一步等价于窗口滑动到当前字符分组的末尾。消化长按产生的多余字符上一步结束后j恰好停在当前字符分组的第一个新字符上。如果typed中剩余的连续字符仍与typed[j-1]相同说明这些是长按产生的重复字符让j继续向前跳过它们。收尾判定循环结束后只有i走完整个name且j走完整个typed才返回true。源码逐行剖析仓库中的核心实现位于 925. Long Pressed Name.go完整代码如下package leetcode func isLongPressedName(name string, typed string) bool { if len(name) 0 len(typed) 0 { return true } if (len(name) 0 len(typed) ! 0) || (len(name) ! 0 len(typed) 0) { return false } i, j : 0, 0 for i len(name) j len(typed) { if name[i] ! typed[j] { return false } for i len(name) j len(typed) name[i] typed[j] { i j } for j len(typed) typed[j] typed[j-1] { j } } return i len(name) j len(typed) }下面分三段解读。1. 空字符串边界预处理if len(name) 0 len(typed) 0 { return true } if (len(name) 0 len(typed) ! 0) || (len(name) ! 0 len(typed) 0) { return false }这段代码处理了三种极端情况name和typed都为空空名字对应空输入直接返回true朋友根本没有打字也就谈不上长按name为空但typed非空输入中凭空出现了字符不可能是空名字的长按结果返回falsename非空但typed为空名字存在但输入为空同样返回false。这两个判断保证了后续双指针循环中i、j的取值始终合法也避免了主循环中可能出现的越界访问。2. 主循环对齐 滑动 消化长按i, j : 0, 0 for i len(name) j len(typed) { if name[i] ! typed[j] { return false } for i len(name) j len(typed) name[i] typed[j] { i j } for j len(typed) typed[j] typed[j-1] { j } }主循环体内是三个连续动作首字符比对name[i] ! typed[j]时直接返回false。这是滑动窗口的窗口起点必须匹配约束同步推进内层第一个for让两个指针在字符相同的前提下一起前进i和j严格同步保证name中的每个字符在typed中都有对应位置跳过重复内层第二个for只推进j。当i已经滑过当前分组的最后一个字符或name已耗尽而typed中仍连续出现与typed[j-1]相同的字符时说明这些多出来的字符是长按产生的予以跳过。注意typed[j-1]一定是上一个已匹配的字符因为j是从一个两串相同字符的位置走过来的此时j 1恒成立不会越界。3. 收尾判定return i len(name) j len(typed)循环退出时存在三种可能必须用这个最终条件区分i走完且j走完完全匹配返回truei走完但j没走完需要看typed剩余字符是否都是长按产生的重复字符——这正是内层第二个for消化过的情况只要消化干净就能通过若消化不干净出现新字符会在下一轮主循环的name[i] ! typed[j]处被拦截并返回falsei没走完但j走完typed提前耗尽name中还有字符没匹配上返回false。测试用例佐证边界情况的判定规则README 中特别提醒这一题的测试用例修改过一次需要注意当name结束以后如果typed还有多余的不同的字符这种情况要输出false。也就是说typed只能比name多出长按导致的重复字符绝不能多出新字符。仓库中的 925. Long Pressed Name_test.go 共包含 11 组用例完整覆盖了题目 4 个示例、长按边界与空串边界输入name输入typed期望结果用例考察点alexaaleextrue题目示例 1a、e被长按alexalexxrfalsename结束后typed出现新字符ralexalexxxxrfalsename结束后先有长按的x再出现新字符ralexalexxxxxtruename结束后typed只剩长按的重复字符saeedssaaeddfalse题目示例 2e计数不足leeleelleeeleetrue题目示例 3字符交替出现且计数足够laidenlaidentrue题目示例 4未发生任何长按kikcxmvzikiikcxxmmvvzzfalse混合长按但顺序/计数不满足i组多出字符true双空串边界afalse空名字 非空输入边界afalse非空名字 空输入边界其中最值得关注的是第二、三、四组用例——它们正是 README 反复强调的测试用例修改部分(alex, alexxr)与(alex, alexxxxr)name已经全部匹配完typed中先出现了大量重复的x可以消化但随后出现的r是name中不存在的字符因此返回false(alex, alexxxxx)name匹配完后typed中剩余的全是x的长按重复可以被正常消化因此返回true。这组对照用例精准地刻画了长按只允许重复已有字符不允许引入新字符这一核心语义。复杂度分析时间复杂度O(n m)其中n len(name)m len(typed)。两个指针i、j各自只会单调递增每个字符最多被访问常数次整体线性空间复杂度O(1)只使用了两个整型指针与若干局部变量没有借助额外数据结构。运行与验证在 LeetCode-Go 仓库中该题以标准 Go 测试形式组织。运行以下命令即可执行全部 11 组用例并验证输出go test -v -run Test_Problem925 ./leetcode/0925.Long-Pressed-Name/测试输出会以【input】:... 【output】:...的形式逐组打印输入与结果见 925. Long Pressed Name_test.go。仓库根目录的 gotest.sh 脚本提供了批量跑全部题解测试的方式go.mod 声明了go 1.19的构建环境可直接复用。延伸思考除了双指针解法本题还有一种等价的分组计数思路分别将name和typed压缩为字符, 连续出现次数的分组序列然后逐一比较——要求分组数相等、对应分组字符相同、且typed分组的计数不小于name分组的计数。两种思路本质等价但双指针版本只需一次遍历、无额外空间是面试中最推荐的写法。从源码结构看本题实现刻意将空串边界单独前置处理925. Long Pressed Name.go主循环内再通过同步推进 消化长按两段内层循环处理核心逻辑这种先挡边界、再写主逻辑的写法也值得在其他字符串双指针题目中复用。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 925. Long Pressed Name 长按键入：LeetCode-Go 双指针题解与边界分析
LeetCode 925. Long Pressed Name 长按键入LeetCode-Go 双指针题解与边界分析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 925 题 Long Pressed Name长按键入展开以 LeetCode-Go 仓库中 0925.Long-Pressed-Name 目录 下的官方题解为主体讲解如何用双指针滑动窗口判断长按键盘产生的输入是否可能由给定的名字打出。读完本文你将掌握该题的完整解题思路、Go 源码逐行实现、易错边界用例的判定规则以及如何在本仓库中直接运行测试验证结论。题目描述与约束题目原文摘自 README.mdYour friend is typing his name into a keyboard. Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times. You examine the typed characters of the keyboard. Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.翻译过来就是你的朋友正在用键盘输入自己的名字。有时在输入某个字符 c 时按键可能被长按导致该字符被重复输入 1 次或多次。现在给你观察到的实际键入结果typed判断它是否可能是朋友的名字name经过若干字符也可能没有字符长按后产生的。题目的约束条件如下name.length 1000typed.length 1000name和typed中的字符均为小写字母由于数据规模只有 1000本题对算法复杂度的要求并不苛刻但核心难点在于正确理解长按的语义并处理各种边界情况。题目大意中文解读给定 2 个字符串后者的字符串中包含前者的字符串。比如在打字的过程中某个字符会多按了几下。判断后者字符串是不是比前者字符串存在这样的长按键盘的情况。更严谨地说typed可以看成是name中每个字符的分组被展开的结果——name中每个字符在typed中出现的次数必须不小于 1等于 1 表示没有长按大于 1 表示长按了且字符出现的相对顺序不能改变。因此typed中不允许出现name中没有的字符typed中同一字符组的长度不能少于name中对应字符在原始串中的计数。解题思路双指针滑动窗口扫描README 中明确指出这一题可以借助滑动窗口的思想2 个字符串一起比较如果遇到有相同的字符串窗口继续往后滑动直到遇到了第一个不同的字符如果遇到两个字符串不相等的情况可以直接返回 false。具体到实现上我们维护两个指针指针i指向name中当前正在匹配的字符指针j指向typed中当前正在匹配的字符。算法流程如下字符对齐比较name[i]与typed[j]。如果两者不同说明typed中出现了name中不存在的字符或顺序错乱直接返回false。吃掉相同字符在name和typed都未越界的前提下只要name[i] typed[j]就让i和j同步前进直到遇到第一个不相同的字符。这一步等价于窗口滑动到当前字符分组的末尾。消化长按产生的多余字符上一步结束后j恰好停在当前字符分组的第一个新字符上。如果typed中剩余的连续字符仍与typed[j-1]相同说明这些是长按产生的重复字符让j继续向前跳过它们。收尾判定循环结束后只有i走完整个name且j走完整个typed才返回true。源码逐行剖析仓库中的核心实现位于 925. Long Pressed Name.go完整代码如下package leetcode func isLongPressedName(name string, typed string) bool { if len(name) 0 len(typed) 0 { return true } if (len(name) 0 len(typed) ! 0) || (len(name) ! 0 len(typed) 0) { return false } i, j : 0, 0 for i len(name) j len(typed) { if name[i] ! typed[j] { return false } for i len(name) j len(typed) name[i] typed[j] { i j } for j len(typed) typed[j] typed[j-1] { j } } return i len(name) j len(typed) }下面分三段解读。1. 空字符串边界预处理if len(name) 0 len(typed) 0 { return true } if (len(name) 0 len(typed) ! 0) || (len(name) ! 0 len(typed) 0) { return false }这段代码处理了三种极端情况name和typed都为空空名字对应空输入直接返回true朋友根本没有打字也就谈不上长按name为空但typed非空输入中凭空出现了字符不可能是空名字的长按结果返回falsename非空但typed为空名字存在但输入为空同样返回false。这两个判断保证了后续双指针循环中i、j的取值始终合法也避免了主循环中可能出现的越界访问。2. 主循环对齐 滑动 消化长按i, j : 0, 0 for i len(name) j len(typed) { if name[i] ! typed[j] { return false } for i len(name) j len(typed) name[i] typed[j] { i j } for j len(typed) typed[j] typed[j-1] { j } }主循环体内是三个连续动作首字符比对name[i] ! typed[j]时直接返回false。这是滑动窗口的窗口起点必须匹配约束同步推进内层第一个for让两个指针在字符相同的前提下一起前进i和j严格同步保证name中的每个字符在typed中都有对应位置跳过重复内层第二个for只推进j。当i已经滑过当前分组的最后一个字符或name已耗尽而typed中仍连续出现与typed[j-1]相同的字符时说明这些多出来的字符是长按产生的予以跳过。注意typed[j-1]一定是上一个已匹配的字符因为j是从一个两串相同字符的位置走过来的此时j 1恒成立不会越界。3. 收尾判定return i len(name) j len(typed)循环退出时存在三种可能必须用这个最终条件区分i走完且j走完完全匹配返回truei走完但j没走完需要看typed剩余字符是否都是长按产生的重复字符——这正是内层第二个for消化过的情况只要消化干净就能通过若消化不干净出现新字符会在下一轮主循环的name[i] ! typed[j]处被拦截并返回falsei没走完但j走完typed提前耗尽name中还有字符没匹配上返回false。测试用例佐证边界情况的判定规则README 中特别提醒这一题的测试用例修改过一次需要注意当name结束以后如果typed还有多余的不同的字符这种情况要输出false。也就是说typed只能比name多出长按导致的重复字符绝不能多出新字符。仓库中的 925. Long Pressed Name_test.go 共包含 11 组用例完整覆盖了题目 4 个示例、长按边界与空串边界输入name输入typed期望结果用例考察点alexaaleextrue题目示例 1a、e被长按alexalexxrfalsename结束后typed出现新字符ralexalexxxxrfalsename结束后先有长按的x再出现新字符ralexalexxxxxtruename结束后typed只剩长按的重复字符saeedssaaeddfalse题目示例 2e计数不足leeleelleeeleetrue题目示例 3字符交替出现且计数足够laidenlaidentrue题目示例 4未发生任何长按kikcxmvzikiikcxxmmvvzzfalse混合长按但顺序/计数不满足i组多出字符true双空串边界afalse空名字 非空输入边界afalse非空名字 空输入边界其中最值得关注的是第二、三、四组用例——它们正是 README 反复强调的测试用例修改部分(alex, alexxr)与(alex, alexxxxr)name已经全部匹配完typed中先出现了大量重复的x可以消化但随后出现的r是name中不存在的字符因此返回false(alex, alexxxxx)name匹配完后typed中剩余的全是x的长按重复可以被正常消化因此返回true。这组对照用例精准地刻画了长按只允许重复已有字符不允许引入新字符这一核心语义。复杂度分析时间复杂度O(n m)其中n len(name)m len(typed)。两个指针i、j各自只会单调递增每个字符最多被访问常数次整体线性空间复杂度O(1)只使用了两个整型指针与若干局部变量没有借助额外数据结构。运行与验证在 LeetCode-Go 仓库中该题以标准 Go 测试形式组织。运行以下命令即可执行全部 11 组用例并验证输出go test -v -run Test_Problem925 ./leetcode/0925.Long-Pressed-Name/测试输出会以【input】:... 【output】:...的形式逐组打印输入与结果见 925. Long Pressed Name_test.go。仓库根目录的 gotest.sh 脚本提供了批量跑全部题解测试的方式go.mod 声明了go 1.19的构建环境可直接复用。延伸思考除了双指针解法本题还有一种等价的分组计数思路分别将name和typed压缩为字符, 连续出现次数的分组序列然后逐一比较——要求分组数相等、对应分组字符相同、且typed分组的计数不小于name分组的计数。两种思路本质等价但双指针版本只需一次遍历、无额外空间是面试中最推荐的写法。从源码结构看本题实现刻意将空串边界单独前置处理925. Long Pressed Name.go主循环内再通过同步推进 消化长按两段内层循环处理核心逻辑这种先挡边界、再写主逻辑的写法也值得在其他字符串双指针题目中复用。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考