题目描述
你的朋友正在用键盘输入他的名字name。有时候，在输入一个字母c时，由于按键时间过长，可能会导致一个字母被输入多次。
你需要判断一个键盘输入的字符串typed，是否有可能是你朋友的名字（某些字母由于按键时间太长，被多输入了几次）。
注意
name.length <= 1000typed.length <= 1000name和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();
}
};
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; } }棒
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总，让我摆脱上面繁杂的判断。妙~