Leetcode日记–925. Long Pressed Name

发布于 2020-10-21  110 次阅读


碎碎念:小新AIr15的屏幕是真的香,高色域,yyds!

题目如下:

Your friend is typing his name into a keyboard.  Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times.

You examine the typed characters of the keyboard.  Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.

Example 1:

Input: name = "alex", typed = "aaleex"
Output: true
Explanation: 'a' and 'e' in 'alex' were long pressed.

Example 2:

Input: name = "saeed", typed = "ssaaedd"
Output: false
Explanation: 'e' must have been pressed twice, but it wasn't in the typed output.

Example 3:

Input: name = "leelee", typed = "lleeelee"
Output: true

Example 4:

Input: name = "laiden", typed = "laiden"
Output: true
Explanation: It's not necessary to long press any character.
 

Constraints:

1 <= name.length <= 1000
1 <= typed.length <= 1000
The characters of name and typed are lowercase letters.

思路:

我的思路是每次先遍历name,记下来当前这个字符(或一样的字符)共有多少个,然后再遍历typed,记下typed的个数,如若typed当前字符的个数大于name,则进入对新出现的字符的检查。

但是这个方法因为每次要检查当前的下一个位置,因此边界问题非常麻烦(debug不出来)。

我自己的(没有debug结束的)代码如下:

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        // if(name==null|typed==null)
            // return false;
        // i和j是用来遍历name和typed的指针
        int nCount=1,tCount=1,i=0,j=0,n=name.length(),m=typed.length();
        while(i<n-1&&j<m-1){
            // 先计数当前name的字符出现了多少次
            while(i<n-1&&name.charAt(i)==name.charAt(i+1)){
                ++i;
                ++nCount;
            }
            char targetChar = name.charAt(i);
            ++i;
            // 进行对typed的判定
            while(j<m-1&&typed.charAt(j)==typed.charAt(j+1)){
                if(typed.charAt(j)!=targetChar)
                    return false;
                ++j;
                ++tCount;
            }
            ++j;
            if(tCount<nCount)
                return false;
            else{
                nCount=1;
                tCount=1;
            }
        }
        return true;
    }
}

官方解法的思路是每次移动一步(而不是我那样的每次检查一个字符)。

typed字符串中的字符有两种可能性:

①如果是和name匹配的,则name和typed的指针都向后移动

②如果typed不与name匹配,但是与自己前一位匹配,则typed指针自己向后移动一位。

最后,如果name的指针等于name的长度,说明整个name都被匹配了,可以返回true。

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        int i = 0, j = 0;
        while (j < typed.length()) {
            if (i < name.length() && name.charAt(i) == typed.charAt(j)) {
                i++;
                j++;
            } else if (j > 0 && typed.charAt(j) == typed.charAt(j - 1)) {
                j++;
            } else {
                return false;
            }
        }
        return i == name.length();
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/long-pressed-name/solution/chang-an-jian-ru-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


你好哇!欢迎来到雷公马碎碎念的地方:)