Easy

题目描述

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

你需要检查键盘输入的字符。如果这可能是你朋友的名字（其中一些字符可能被长按），则返回 True。

示例 1:

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

示例 2:

输入: name = "saeed", typed = "ssaaedd"
输出: false
解释: 'e' 必须被按两次，但在输入中没有。

约束条件:

  • 1 <= name.length, typed.length <= 1000
  • name 和 typed 只包含小写英文字母。

解题思路

这道题的核心思想是使用双指针来模拟键盘输入过程。我们需要验证 typed 字符串是否可能是 name 字符串的长按版本。

解题思路：

  1. 双指针遍历：使用两个指针 i 和 j 分别指向 name 和 typed 的当前位置
  2. 字符匹配：当 name[i] == typed[j] 时，两个指针都向前移动
  3. 长按处理：当字符不匹配时，检查 typed[j] 是否等于前一个已匹配的字符，如果是则说明发生了长按，只移动 j 指针
  4. 边界检查：最终需要确保 name 中的所有字符都被匹配完

关键点：

  • 必须按顺序匹配，不能跳过 name 中的任何字符
  • typed 中多余的字符只能是前一个匹配字符的重复
  • 需要处理字符串末尾的情况

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

代码实现

class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        int i = 0, j = 0;
        
        while (j < typed.length()) {
            if (i < name.length() && name[i] == typed[j]) {
                i++;
                j++;
            } else if (j > 0 && typed[j] == typed[j-1]) {
                j++;
            } else {
                return false;
            }
        }
        
        return i == name.length();
    }
};

class Solution:
    def isLongPressedName(self, 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)

public class Solution {
    public bool IsLongPressedName(string name, string typed) {
        int i = 0, j = 0;
        
        while (j < typed.Length) {
            if (i < name.Length && name[i] == typed[j]) {
                i++;
                j++;
            } else if (j > 0 && typed[j] == typed[j-1]) {
                j++;
            } else {
                return false;
            }
        }
        
        return i == name.Length;
    }
}

var isLongPressedName = function(name, typed) {
    let i = 0, j = 0;
    
    while (j < typed.length) {
        if (i < name.length && name[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m)其中 n 是 name 的长度，m 是 typed 的长度，需要遍历两个字符串
空间复杂度O(1)只使用了常数个额外变量

相关题目