双指针算法解决LeetCode长按键入问题

1. 问题背景与需求分析

"长按键入"是LeetCode上经典的字符串处理问题（编号925）。题目描述为：你的朋友正在使用键盘输入名字name，偶尔在键入字符时会长时间按下某个键，导致字符可能被重复输入一次或多次。我们需要检查键入的字符串typed是否是name字符串经过长按键入后得到的合法结果。

这个问题的实际应用场景非常广泛：

  • 手机键盘输入时的误触检测
  • 密码输入时的重复字符校验
  • 语音识别中的持续音处理
  • 硬件键盘的防抖检测

2. 双指针解法核心思路

2.1 算法设计原理

双指针法之所以适合解决这个问题，是因为我们需要同时遍历两个字符串，比较它们的字符是否匹配，同时处理可能的重复字符。具体来说：

  1. 初始化两个指针i和j，分别指向name和typed的开头
  2. 逐个比较字符：
    • 如果字符匹配，两个指针都前进
    • 如果不匹配，检查typed当前字符是否是name前一个字符的重复
  3. 最终检查是否两个指针都到达了各自字符串的末尾

这种解法的时间复杂度是O(n+m)，空间复杂度是O(1)，是最优解。

2.2 边界条件处理

在实际编码中需要特别注意以下边界情况：

  • name为空字符串时，typed也必须为空
  • typed比name短时直接返回false
  • 开头字符不匹配时直接返回false
  • 连续重复字符的数量typed必须≥name中的数量

3. 完整代码实现与解析

3.1 Python实现示例

def isLongPressedName(name: str, typed: str) -> bool: i = j = 0 while j < len(typed): if i < len(name) and name[i] == typed[j]: i += 1 j += 1 elif j > 0 and typed[j] == typed[j-1]: j += 1 else: return False return i == len(name)

3.2 关键代码解读

  1. 双指针初始化：i和j分别追踪name和typed的位置
  2. 主循环条件：只要typed还有字符就继续处理
  3. 第一个if：字符匹配时的处理
  4. elif：处理合法重复字符的情况
  5. else：遇到非法字符直接返回false
  6. 最终检查：name的所有字符必须都被匹配

4. 测试用例设计

4.1 常规测试用例

assert isLongPressedName("alex", "aaleex") == True # 基本通过案例 assert isLongPressedName("saeed", "ssaaedd") == False # e被a打断 assert isLongPressedName("leelee", "lleeelee") == True # 多组重复

4.2 边界测试用例

assert isLongPressedName("", "") == True # 双空 assert isLongPressedName("a", "b") == False # 完全不匹配 assert isLongPressedName("pypl", "ppyypll") == True # 混合重复 assert isLongPressedName("alex", "alexxr") == False # 结尾多余字符

5. 算法优化与变种

5.1 性能优化技巧

虽然双指针已经是O(n)解法，但还可以进行微优化：

  • 添加长度提前判断：if len(typed) < len(name): return False
  • 使用for循环代替while可以减少变量声明
  • 在比较字符时使用直接内存访问而非索引操作

5.2 问题变种思考

这个问题可以有多种变体，适合面试扩展：

  1. 允许最多k次错误的长按键入
  2. 统计name中每个字符的最小和最大重复次数
  3. 找出typed中所有可能对应的name
  4. 处理退格键情况的字符串比较

6. 实际工程应用

6.1 输入法纠错系统

在手机输入法中，可以应用类似算法处理：

  1. 用户连续输入相同字符时的自动校正
  2. 滑动输入时的冗余字符过滤
  3. 九宫格输入时的长按数字处理

6.2 日志分析场景

在服务器日志分析中，可能遇到重复的请求记录：

  1. 检测是否是正常的重试机制
  2. 区分恶意重复请求和正常操作
  3. 压缩重复的日志条目

7. 常见错误与调试技巧

7.1 典型错误模式

  1. 指针越界：忘记检查i < len(name)导致索引错误
  2. 初始条件遗漏：没有处理空字符串情况
  3. 顺序错误：先检查重复再检查匹配会导致逻辑错误
  4. 终止条件错误：只检查了j == len(typed)而忘记检查i

7.2 Debugging方法

  1. 打印指针位置和当前字符：
    print(f"i={i}, j={j}, name[i]={name[i]}, typed[j]={typed[j]}")
  2. 可视化两个字符串的比对过程
  3. 使用小规模测试用例逐步验证
  4. 画状态转移图理清逻辑

8. 扩展学习建议

  1. 类似的双指针题目：

    • 判断子序列（LeetCode 392）
    • 合并两个有序数组（LeetCode 88）
    • 盛最多水的容器（LeetCode 11）

  2. 字符串处理进阶：

    • 正则表达式匹配
    • 编辑距离计算
    • KMP算法

  3. 系统设计中的应用：

    • 文件diff工具的实现
    • 版本控制系统中的冲突检测
    • 生物信息学中的序列比对