LeetCode 925. Long Pressed Name

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 925. Long Pressed Name 原题链接简单

作者：

yxc , 2018-10-30 01:38:59 , 所有人可见 , 阅读 1681

题目描述

你的朋友正在用键盘输入他的名字name。有时候，在输入一个字母c时，由于按键时间过长，可能会导致一个字母被输入多次。

你需要判断一个键盘输入的字符串typed，是否有可能是你朋友的名字（某些字母由于按键时间太长，被多输入了几次）。

注意

name.length <= 1000
typed.length <= 1000
name和typed均由小写字母构成。

样例1

输入：name = "alex", typed = "aaleex"
输出：true
解释："alex"中的'a'和'e'被过多输入了。

样例2

输入：name = "saeed", typed = "ssaaedd"
输出：false
解释：'e' 至少需要输入两次，但typed中只有一次。

样例3

输入：name = "leelee", typed = "lleeelee"
输出：true

样例4

输入：name = "laiden", typed = "laiden"
输出：true
解释：不用必须有字母被过多输入。

算法

(模拟) $O(n)$

同时从前往后遍历两个字符串，每次分别找出两个字符串中相同字母的一段，如果：

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

则说明该段字母合法，否则说明该段字母不合法。

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

时间复杂度分析：两个字符串都只遍历了一遍，所以总时间复杂度是 $O(n)$。

C++ 代码

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

4 评论

YYC 2020-07-24 11:25

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;
    }
}

yxc 2020-08-18 10:32

棒

YYC 2020-07-24 11:11

class Solution {
    public boolean isLongPressedName(String name, String typed) {

        int n = typed.length();
        int i = name.length()  - 1;
        int j = n - 1;
        while (i >= 0 && j >= 0){
            // 如果当前两个字符相等，则均往左走一步
            if (name.charAt(i) == typed.charAt(j)){
                i--;
                j--;
            } else {
                // 如果当前两个字符不等，且typed的当前字符与后一个字符相等，
                // 说明是Long Pressed的字母，则j--
                if (j + 1 < n && typed.charAt(j) == typed.charAt(j + 1)){
                    j--;
                // 否则不符题意
                } else {
                    return false;
                }
            }
        }

        // 如果i >= 0，说明name没有遍历完，肯定不符题意。
        if (i >= 0) return false;

        // 判断typed的头部是否有Long Pressed的字母。
        while (j >= 0){
            if (typed.charAt(j) != typed.charAt(j + 1)){
                return false;
            }
            j--;
        }
        return true;
    }
}

多谢Y总，让我摆脱上面繁杂的判断。