这是悦乐书的第355次更新，第380篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第217题（顺位题号是925）。你的朋友正在键盘上输入他的名字。 有时，在键入字符c时，键可能会被长按，键入的字符将被输入1次或更多次。
你检查键盘的键入字符。 如果可能是你的朋友姓名，则返回True，其中一些字符（可能没有）被长按。例如：
输入：name =“alex”，typed =“aaleex”
输出：true
说明：'alex'中的'a'和'e'被长按。
输入：name =“saeed”，typed =“ssaaedd”
输出：false
说明：'e'必须按两次，但它不在输入的输出中。
输入：name =“leelee”，typed =“lleeelee”
输出：true
输入：name =“laiden”，typed =“laiden”
输出：true
说明：没有必要长按任何字符。
注意：
name.length <= 1000
typed.length <= 1000
name和typed的字符是小写字母。
02 第一种解法
题目的意思是typed中的某些字母会在name的基础上重复出现，当然，最理想的状态是name和typed完全相等。
想要结果返回true，需要满足以下条件：
对应位置的字母要相等，
typed中对应位置的字母出现次数只能等于或多于name中对应的字母。name中有的字母以及出现次数，typed中必须有。在没处理完
name中的字母时，typed不能已经处理完了。
反之，返回false就是上述三种情况的反例，只要出现一种就可以直接返回false。
思路：遍历name中的字母，并统计当前字母出现的次数，直到遇到不同的字母，接着遍历typed中的字母，同样计数，然后判断前面我们分析的三种正常情况的反例，如果符合就直接返回false，三种反例都不符合，就将计数重置为1，相应的索引自加1。
此解法的时间复杂度为O(N)，其中N代表字符串name和typed的长度之和，空间复杂度为O(1)。
public boolean isLongPressedName(String name, String typed) {
if (name.equals(typed)) {
return true;
}
int count = 1, n = name.length();
int j = 0, len = typed.length(), num = 1;
for (int i=0; i<=n-1; i++) {
while (i<n-1 && name.charAt(i) == name.charAt(i+1)) {
count++;
i++;
}
while (j<len-1 && typed.charAt(j) == typed.charAt(j+1)) {
num++;
j++;
}
if (j>len-1 || num < count || name.charAt(i) != typed.charAt(j) ) {
return false;
}
count = 1;
num = 1;
j++;
}
return true;
}03 第二种解法
我们也可以处理typed字符串，统计typed中和name相等的字母个数，如果最后和name的长度相等，就表明name中的字母全部都出现在了typed中。
此解法的时间复杂度为O(N)，其中N代表字符串typed的长度，空间复杂度为O(1)。
public boolean isLongPressedName2(String name, String typed) {
if (name.equals(typed)) {
return true;
}
int j = 0, n = name.length();
int len = typed.length();
for (int i=0; i<len; i++) {
if (j<n && typed.charAt(i) == name.charAt(j)) {
j++;
}
}
return j == n;
}04 小结
算法专题目前已连续日更超过六个月，算法题文章223+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
- 还没有人评论，欢迎说说您的想法！
客服
