Leetcode 925 Long Pressed Name

发表于 |

你的朋友正在使用键盘输入他的名字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
解释：并不一定会长按某个键。

提示：

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

题意分析：
对于第一个字符串，使其中的某些字符连续出现多次，问第二个字符串是不是满足其中的一种可能。

思路分析：
这道题看似很简单，直接双指针依次判断就好，但我总感觉应该还会有更简单的方法。

使用i,j分别指向name和type，如果指向的字符不相等则直接返回False

若相等，则考虑到多次键入的可能性，只要name[i] == name[i+1] or typed[j] == type[j+1]，i,j就继续向右移动。但这里要注意一个点，那就是i移动的距离一定要小于等于j移动的距离，否则就会像示例2中一样返回False.

最后，两个指针应当同时走到字符串的末尾，否则说明还有字符不匹配，则返回False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 24ms
class Solution(object):
    def isLongPressedName(self, name, typed):
        n,m = len(name), len(typed)
        i = j = 0
        while i < n and j < m:
            if name[i] != typed[j]: return False
            cnt_i, cnt_j = i, j
            i += 1; j += 1
            while i < n and name[i] == name[i-1]: i += 1
            while j < m and typed[j] == typed[j-1]: j += 1
            # 判断i移动的距离和j移动的距离
            if i - cnt_i > j - cnt_j: return False
        # 是否匹配结束
        if i == n and j == m: return True
        return False