问题描述

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：name = "leelee", typed = "lleeelee"
输出：true

示例 4：

输入：name = "laiden", typed = "laiden"
输出：true
解释：长按名字中的字符并不是必要的。

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/long-pressed-name
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

• 设置游标 i，j 初始时都为 0
• 重复执行下面流程，直到 i == len(name) 或 j == len(typed)：
  • 获取 name 中以 i 为起始索引的所有字符都相同的最长子串，得到字符 char1 和终止索引 end1
  • 获取 typed 中以 j 为起始索引的所有字符都相同的最长子串，得到字符 char2 和终止索引 end2
  • 如果 char1 != char2，说明输错字符，返回 False
  • 如果 end1 - i > end2 - j，说明少输入字符，返回 False
  • 令 i = end1 + 1，j = end2 + 1
• 最终如果 i == len(name) 并且 j == len(typed) 说明两个字符串都已遍历到末尾，返回 True；否则说明某个字符串“更长”，返回 False

Python 实现

class Solution(object):
    def isLongPressedName(self, name, typed):
        """
        :type name: str
        :type typed: str
        :rtype: bool
        """
        i = 0
        j = 0
        end1 = 0
        end2 = 0

        while i < len(name) and j < len(typed):
            char1, end1, = self.get_front(name, i)
            char2, end2 = self.get_front(typed, j)
            if char1 != char2 or (end1 - i) > (end2 - j):
                return False
            i = end1 + 1
            j = end2 + 1

        return i == len(name) and j == len(typed)

    def get_front(self, s, start):
        if start >= len(s):
            raise RuntimeError()

        char = s[start]
        end = start
        while end < len(s):
            if end == len(s) - 1 or s[end + 1] != s[end]:
                return char, end
            end = end + 1