0925. 长按键入【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 双指针

1. 📝 题目描述

• leetcode

你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。

你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。

---

示例 1：

输入：name = "alex", typed = "aaleex"
输出：true
解释：'alex' 中的 'a' 和 'e' 被长按。

---

示例 2：

输入：name = "saeed", typed = "ssaaedd"
输出：false
解释：'e' 一定需要被键入两次，但在 typed 的输出中不是这样。

---

提示：

• 1 <= name.length, typed.length <= 1000
• name 和 typed 的字符都是小写字母

2. 🎯 s.1 - 双指针

js

/**
 * @param {string} name
 * @param {string} typed
 * @return {boolean}
 */
var isLongPressedName = function (name, typed) {
  let i = 0 // 指向 name
  let j = 0 // 指向 typed

  while (j < typed.length) {
    if (i < name.length && name[i] === typed[j]) {
      // 正常匹配，双指针同时前进
      i++
      j++
    } else if (j > 0 && typed[j] === typed[j - 1]) {
      // 长按：typed 当前字符可与前一个相同，继续消耗 typed
      j++
    } else {
      return false
    }
  }

  return i === name.length
}

• 时间复杂度：$O(n+m)$，其中 $n=|name|$，$m=|typed|$
• 空间复杂度：$O(1)$

算法思路：

• 双指针：i 遍历 name，j 遍历 typed
  • 当 name[i] === typed[j] 时，同时前进 i 和 j
  • 当 typed[j] == typed[j-1] 时，视为长按，只前进 j
  • 出现其它不匹配的情况时，立即返回 false
• 最终需 i === name.length 才表示 name 全部匹配完成