leetcode之Long Pressed Name

「爱情、让人受尽委屈。」 2022-11-19 11:28 133阅读 0赞

问题来源：[Long Pressed Name][]  
问题描述：判断字符串name是否是由长按字符串typed得来。长按含义是name的每个字符可能会重复1到多次。  
看到该题目第一眼还以为是[Is Subsequence][]，判断短串是否是长串的子序列，随即用该思路实现了一版，结果发现不对。原因在于在本题中要求的长按模式比子序列更为严格：**首先name的开头和结尾字符要和typed的开头和结尾字符相同，此外typed的字符顺序要和name相同，中间不得插入其他字符**。后来又想到另一种思路：把typed中前后相同的字符进行压缩，看压缩之后是否和name相同，结果一试也是不对。这种思路不对的原因是name中可能会出现连续相同的字符(比如leetcode中的ee)，这种情况下不能把typed中相同的字符都压缩成一个字符。

## 解法一 ##

上述第二种思路虽然不正确，但是却可以启发我们按照这种思路继续尝试，只要能处理好name中连续相同的字符即可。如果name中出现连续相同的字符，我们就让相同字符中前面的几个都只映射typed中一个字符，让相同字符中的最后一个映射typed中的一个或者多个字符。按照这个思路实现的正确代码如下：

bool isLongPressedName(string name, string typed) {
        
        int nlen=name.length(),tlen=typed.length();
    
        int j=0;//typed索引
        for(int i=0;i<nlen-1;i++)
        {
        
            if(typed[j]!=name[i])
            {
        
                return false;
            }
                
    		//当name前后字符相同时，前面的字符都只对应typed中的一个字符
            if(name[i]==name[i+1])
            {
        
                j++;
            }
            else
            {
        
                while(j<tlen&&name[i]==typed[j])
                {
        
                    j++;
                }
            }
    
    		//bad case2
            if(j==tlen) return false;
        }
    
    	//bad case1
        while(j<tlen&&name[nlen-1]==typed[j])
        {
        
            j++;
        }
    
        return j==tlen;
    }

上述代码把name当做主遍历字符串，在每个位置判断是否匹配，并移动typed的索引。在代码实现的过程中，给定的bad case可能有这么几类：

1.  name匹配到末尾，但是typed没有匹配到末尾，例如：”abc”和”aabbccd”；
2.  name没有匹配到末尾，但是typed到末尾，例如：“pyplrz"和"ppyypllr”。  
    只要能处理好各种bad case，把代码写对就水到渠成了。

## 解法二 ##

在实现了上述方法之后又看了看题解，发现还有另一种解法：我们使用两个下标 i，j追踪name和typed的位置。当name\[i\]=typed\[j\]时，说明两个字符串存在一对匹配的字符，此时将i，j都加1。否则，如果typed\[j\]=typed\[j−1\]，说明存在一次长按键入，此时只将j加1。最后，如果i=name.length，说明name的每个字符都被匹配了。按照该思路实现的正确代码如下：

bool isLongPressedName(string name, string typed) {
        
    	//第一个字符必须相同，同时避免后续代码引入额外的边界判断
        if(name[0]!=typed[0]) return false;
    
    	int nlen=name.length(),tlen=typed.length();
        int i=1,j=1;
        while(i<nlen||j<tlen)
        {
        
            if(name[i]==typed[j]) 
            {
        
                i++;j++;
            }
            else if(typed[j]==typed[j-1])
            {
        
                j++;
            }
            else
            {
        
                return false;
            }
        }
    
        return i==nlen&&j==tlen;
    }

该思路本质上是把typed当做主遍历字符串，相比网上出现的正确代码，上面的代码逻辑判断更为简洁，书写也更加优美，推荐大家采用这种写法。

[Long Pressed Name]: https://leetcode-cn.com/problems/long-pressed-name/
[Is Subsequence]: https://leetcode-cn.com/problems/is-subsequence/