leetcode - [925] Long Pressed Name

2020/06/27

问题描述

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

Update at 2020_0724

多谢Y总,换一种思路:

首先,使用两个指针同时从前往后遍历两个字符串,每次分别找出两个字符串中相同字母的一段,如果:

  • 字母相同
  • name中该段的长度小于等于typed中该段的长度

则说明这段字母是合法的,否则非法。

如果所有相同字母段都合法,则返回true,否则返回false

来看下三种非法的场景:

完整实现:

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        
        int l1 = name.length();
        int l2 = typed.length();
        
        int i = 0, j = 0;
        while (i < l1 && j < l2){
            int ii = i, jj = j;
            while (ii < l1 && name.charAt(ii)  == name.charAt(i))  ii++;
            while (jj < l2 && typed.charAt(jj) == typed.charAt(j)) jj++;
            if (name.charAt(i) != typed.charAt(j) || ii - i > jj - j) return false;
            i = ii; j = jj;
        }
        return i == l1 && j == l2;
    }
}

解法1

这道题还是挺有意思的。

先来梳理下思路:

首先,创建两个变量loTloN,分别指向两个字符串的开始位置。

然后,从左到右依次遍历,分为三种情况:

第一种:

if (typed.charAt(loT) == name.charAt(loN)){
    pre = name.charAt(loN);
    loN++;
    loT++;
}

当两个字母相等时,各往右走一步,并记录当前名字中的字母。

第二种:

else if (typed.charAt(loT) == pre) {
    loT++;
}

如果,两个字母不相等,但是当前输入的字母等于前一个名字中的字母时,

loT往右走一步。

第三种:

若不符合以上两种情况,则返回false

else {
    return false;
}

那么,我们最终判断的条件是什么?

判断loN是否等于name.length()

return loN == hiN;

慢着,还不够,考虑以下场景:

name  = "alex"
typed = "alexxr"

我们还需要将typed遍历完,判断它是否包含其他字母:

while (loT < hiT){
    if (typed.charAt(loT) != pre) {
        return false;
    }
    loT++;
}

来看下完整实现:

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        
        int loN  = 0;
        int loT  = 0;
        int hiN  = name.length();
        int hiT  = typed.length();
        char pre = name.charAt(0);
        
        while (loN < hiN && loT < hiT){
            
            if (typed.charAt(loT) == name.charAt(loN)){
                pre = name.charAt(loN);
                loN++;
                loT++;
            } else if (typed.charAt(loT) == pre) {
                loT++;
            } else {
                return false;
            }
        }
        
        while (loT < hiT){
            if (typed.charAt(loT) != pre) {
                return false;
            }
            loT++;
        }
        
        return loN == hiN;
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory