925.长按键入

发表于： 分类于：
字数： 975 阅读：≈ 2分钟

🏔 925.长按键入

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

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

思路

基本思想

主要就是用代码模拟手动匹配的过程

  1. 两个位置字符匹配时，一起向后移动
  2. 两个位置字符不匹配时，需要去除重复元素
    1. 当不匹配位置在开头，此时直接不符合要求，比如aabc和bc
    2. 当不匹配位置不在开头，此时需要将重复键入的元素去除
      1. 如果重复元素去除之后两个位置不匹配，此时返回false，例如aaabc和ac，在a和c位置不匹配，去除重复元素a之后，又在b和c位置不匹配，此时返回false
      2. 如果去除重复元素之后两个位置匹配，此时二者向后移动一位继续匹配
  3. 当任有一个字符串匹配结束之后，看另外一个字符串是否匹配完成
    1. 当name没有匹配完成，直接返回false，例如aabc和aaab
    2. 当typed没有匹配完成时，此时需要分情况讨论
      1. 当typed后面的元素全都相等时，返回true，例如aabc和aaabcccc
      2. 当typed后面的元素不全都相等时，返回false，例如aabc和aaabcccdc

执行流程

执行流程同上

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        if(typed.size()<name.size())
            return false;
        int i=0,j=0;
        //依次向后匹配，出现不匹配的元素，尝试将typed中的重复项去除再匹配
        while(i<name.size()&&j<typed.size()){
            //两个位置的元素匹配
            if(name[i]==typed[j]){
                ++i;
                ++j;
            }
            //两个位置的元素不匹配
            else{
                //第一个位置就不匹配，说明不是长按
                if(j==0)
                    return false;
                //去掉长按之后的重复项
                while(j<typed.size()&&typed[j]==typed[j-1]){
                    j++;
                }
                //去掉之后相等，需要继续向后匹配
                if(name[i]==typed[j]){
                    ++i;
                    ++j;
                }
                //去掉之后不匹配
                else  
                    return false;
            }
        }
        //结束之后看name和typed是否匹配完毕
        //如果name没有被匹配完，说明不是在输入名字
        if(i<name.size())
            return false;
        if(j<typed.size()){
            while(j<typed.size()){
                if(typed[j]!=typed[j-1])
                    return false;
                ++j;
            }
        }
        //到这里应该返回true
        return true;
    }
};

总结

主要是代码模拟匹配的过程，不匹配时需要去除重复键入的元素，返回false的情况分以下几种：

  1. 当不匹配位置出现在开头时直接返回false
  2. 当去重之后不匹配时也返回false
  3. 当其中一个字符串匹配完成且name没有匹配完成时直接返回false
  4. 当其中一个字符串匹配完成且typed没有匹配完成并且typed剩下的元素不全都相等时返回false