0925. 长按键入 #

标签：双指针、字符串
难度：简单

题目大意 #

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

现在给定代表名字的字符串 name，以及实际输入的字符串 typed。

要求：检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），就返回 True。否则返回 False。

解题思路 #

这道题目的意思是在 typed 里边匹配 name，同时要考虑字符重复问题，以及不匹配的情况。可以使用分离双指针来做。具体做法如下：

使用两个指针 left_1、left_2，left_1 指向字符串 name 开始位置，left_2 指向字符串 type 开始位置。
如果 name[left_1] 等于 name[left_2]，则将 left_1、left_2 同时右移。
如果 nmae[left_1] 不等于 name[left_2]，则：
- 如果 typed[left_2] 和前一个位置元素 typed[left_2 - 1] 相等，则说明出现了重复元素，将 left_2 右移，过滤重复元素。
- 如果 typed[left_2] 和前一个位置元素 typed[left_2 - 1] 不等，则说明出现了多余元素，不匹配。直接返回 False 即可。
当 left_1 == len(name) 或 left_2 == len(typed) 时跳出循环。然后过滤掉 typed 末尾的重复元素。
最后判断，如果 left_1 == len(name) 并且 left_2 == len(typed)，则说明匹配，返回 True，否则返回 False。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool:
        left_1, left_2 = 0, 0

        while left_1 < len(name) and left_2 < len(typed):
            if name[left_1] == typed[left_2]:
                left_1 += 1
                left_2 += 1
            elif left_2 > 0 and typed[left_2 - 1] == typed[left_2]:
                left_2 += 1
            else:
                return False
        while 0 < left_2 < len(typed) and typed[left_2] == typed[left_2 - 1]:
            left_2 += 1

        if left_1 == len(name) and left_2 == len(typed):
            return True
        else:
            return False