你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被 长按 ，而字符可能被输入 1 次或多次。
你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。
示例 1：
**输入：** name = "alex", typed = "aaleex"
**输出：** true
**解释：** 'alex' 中的 'a' 和 'e' 被长按。
示例 2：
**输入：** name = "saeed", typed = "ssaaedd"
**输出：** false
**解释：** 'e' 一定需要被键入两次，但在 typed 的输出中不是这样。
提示：
1 <= name.length, typed.length <= 1000name 和 typed 的字符都是小写字母
方法一：双指针
思路与算法
根据题意能够分析得到：字符串 typed 的每个字符，有且只有两种「用途」：
如果 typed 中存在一个字符，它两个条件均不满足，则应当直接返回 false；否则，当 typed 扫描完毕后，我们再检查 name 的每个字符是否都被「匹配」了。
实现上，我们使用两个下标 i,j 追踪 name 和 typed 的位置。
当 name}[i]=\textit{typed}[j] 时，说明两个字符串存在一对匹配的字符，此时将 i,j 都加 1。
否则，如果 typed}[j]=\textit{typed}[j-1]，说明存在一次长按键入，此时只将 j 加 1。
最后，如果 i=\textit{name}.\text{length，说明 name 的每个字符都被「匹配」了。
代码
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
bool isLongPressedName(string name, string typed) {
int i = 0, j = 0;
while (j < typed.length()) {
if (i < name.length() && name[i] == typed[j]) {
i++;
j++;
} else if (j > 0 && typed[j] == typed[j - 1]) {
j++;
} else {
return false;
}
}
return i == name.length();
}
};
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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();
}
}
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| bool isLongPressedName(char* name, char* typed) {
int n = strlen(name), m = strlen(typed);
int i = 0, j = 0;
while (j < m) {
if (i < n && name[i] == typed[j]) {
i++;
j++;
} else if (j > 0 && typed[j] == typed[j - 1]) {
j++;
} else {
return false;
}
}
return i == n;
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| var isLongPressedName = function(name, typed) {
const n = name.length, m = typed.length;
let i = 0, j = 0;
while (j < m) {
if (i < n && name[i] === typed[j]) {
i++;
j++;
} else if (j > 0 && typed[j] === typed[j - 1]) {
j++;
} else {
return false;
}
}
return i === n;
};
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func isLongPressedName(name string, typed string) bool {
i, j := 0, 0
for j < len(typed) {
if i < len(name) && name[i] == typed[j] {
i++
j++
} else if j > 0 && typed[j] == typed[j-1] {
j++
} else {
return false
}
}
return i == len(name)
}
|
复杂度分析
