[LeetCode] 925. Long Pressed Name

[grandyang]

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.

Note:

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

这道题说是你朋友在用键盘敲入名字的时候，对于某个字母可能会长时间按键，这导可能会有多个相同字母输入，这种情况是允许的，现在给了两个字符串，name 是朋友的名字，typed 是朋友敲入的字符串，问 typed 是否是朋友敲入的名字。其实这道题的本质是，对于 name 中每个位置的字母，对应在 typed 中的出现次数一定要相等或者更多，但是直接统计每个字符出现的次数是不对的，因为位置关系很重要，比如 abb 和 abab，虽然后者中a和b的出现次数都大于等于前者，但还是要返回 false。博主最先想的方法是用两个指针i和j分别提取 name 和 typed 字符串中每个字母出现的次数，如果 typed 中的次数小于 name 中的次数，则直接返回 false 即可，最终循环结束后，i和j应该分别为 name 和 typed 的长度，此时返回 true，否则返回 false，参见代码如下：

解法一：

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

可以写的简洁一些，不需要使用那么多的 while 循环，而是直接用j遍历 typed 中每个字母，i初识时指向 name 的第一个字母，假如i小于m，且 name[i] 等于 typed[j-1] 时，则i自增1，否则的话，若此时j为0（说明第一个字母就不匹配），或者 typed[j] 不等于 typed[j - 1]（说明出现了无法匹配的新字母），则直接返回 false。循环退出后若i等于m则返回 true，否则返回 false，参见代码如下：

解法二：

class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        int i = 0, m = name.size(), n = typed.size();
        for (int j = 0; j < n; ++j) {
            if (i < m && name[i] == typed[j]) ++i;
            else if (!j || typed[j] != typed[j - 1]) return false;
        }
        return i == m;
    }
};

Github 同步地址:

#925

参考资料：

https://leetcode.com/problems/long-pressed-name/

https://leetcode.com/problems/long-pressed-name/discuss/183994/C%2B%2BJavaPython-Two-Pointers

https://leetcode.com/problems/long-pressed-name/discuss/183929/C%2B%2B-2-lines-accepted-and-5-lines-accurate

LeetCode All in One 题目讲解汇总(持续更新中...)