LeetCode 925. 长按键入

约 4 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 字节
标签
字符串 双指针

题目描述

✅ 925. 长按键入

image-20260929105138707

题意分析

判断 typed 是否可能由输入 name 时长按某些按键得到。每个源字符至少输入一次，长按只能让它在原位置连续重复，不能漏字、换序或插入其他字符。

等价地说，两串的连续字符段必须按相同顺序出现，且 typed 每段的长度不能少于 name 对应段。可以用双指针在扫描过程中完成这个判断，不必显式拆分各段。

解法：双指针扫描

核心思路

[!blue]

i 指向 name 中下一个需要匹配的字符，j 从左到右扫描 typed。若 typed[j] == name[i]，优先把它用于正常输入，同时推进两个指针；同一字符段里，先满足源串必需的次数不会损失解，因为余下相同字符仍然可以解释为长按。

若不能正常匹配，当前字符只能是上一按键的额外重复。因此必须满足 j>0 且 typed[j] == typed[j-1]，此时只推进 j。已经接受的前缀保证前一个字符有合法来源，继续重复它也合法；否则当前字符既不是下一个源字符，也不是延续前一次输入，只能返回 false。

每轮之后，已扫描的 typed 前缀都有合法解释，i 是按正常匹配优先能够覆盖的最长源前缀。若某个源字符段所需次数不足，扫描进入下一个不同字符时就无法通过匹配；如果不足发生在末尾，则会由最终的 i == name.length() 检查发现。只有实际输入和源串都处理完，才能返回 true。

解题步骤

  1. 两个指针从头开始。
  2. 当前字符能正常匹配时，同时推进。
  3. 不能正常匹配时，只允许重复 typed 的前一字符。
  4. 扫描结束检查 name 是否已全部匹配。

首个输入字符没有前驱，只能正常匹配。源串匹配完后，实际输入仍可能有末尾长按，因此要继续扫描，但必须先检查 i 的范围，不能再直接访问 name[i]。

代码实现

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(\lvert typed\rvert+1)$，每轮推进实际输入指针。
  • 空间复杂度：$O(1)$。

关键点总结

[!green]

  • 正常匹配优先，保证源串本来就需要的重复字符得到足够输入。
  • 额外字符只能延续上一段，不能单凭源串是子序列就判定成功。
  • 扫描结束还要检查源串是否全部匹配，防止尾部漏字。

易错点总结

[!yellow]

  • 先把重复字符解释为长按，可能少消费源串本身需要的同字符。
  • 不检查 j>0 就读取前一个输入字符，首位会越界。
  • 源串用完后立即拒绝余下字符，会漏掉合法的末尾长按；直接接受余下字符又可能放过新字符。

相似题目

题目 难度 关联与区别
809. 情感丰富的文字 中等 同样逐段比较字符与游程长度，原题的拉伸还要求长段达到特定长度，本题只要求键入次数不少于原名。
443. 压缩字符串 中等 游程编码提供相同字符段及次数，本题比较两串对应段是否兼容长按。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/81424688
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！