力扣 长按键入

题目描述

你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。

你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。

示例 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 解释：长按名字中的字符并不是必要的。

提示：

name.length <= 1000 typed.length <= 1000 name 和 typed 的字符都是小写字母。

思路要点

根据题意能够分析得到: 字符串typed的每个字符, 有且只有两种用途:

作为name的一部分, 此时会匹配name中的一个字符作为长按输入的一部分, 此时它应当与前一个字符相同

如果typed中存在一个字符,它两个条件都不满足, 则应当直接返回false; 否则当typed扫描完毕后, 我们再检查name的每一个字符是否都被匹配了.

我们用两个下表追踪name和typed的位置

当name[i] = typed[j] 时, 说明两个字符存在一对匹配的字符, 此时将i , j 都加一否则,如果typed[j] =typed[j–] , 说明存在一次长按输入,此时只将j 加一

最后, 如果i=name.length, 说明name的每个字符都被匹配了

AC代码:

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

方法二 :

class Solution { public: bool isLongPressedName(string name, string typed) { int j=0; for(int i=0;i<typed.size();i++) { if(j==name.size()||typed[i]!=name[j])//如果两者不相等可能是重复字符也可能是真的不等 { if(i==0||typed[i]!=typed[i-1]) //如果不为重复字符或者是第一个字符则不符合题意 return false; } else //如果是重复字符则两个指针都向前移动一位 { j++; } } return j==name.size(); } };

方法三 :

class Solution { public: bool isLongPressedName(string name, string typed) { int sum=1,j=0;//sum用于记录字符出现的次数 for(int i=0;i<name.length();i++)//注意是小于而不是小于等于,小于等于会造成stack-buffer-overflow报错 { sum=1; while(name[i]==name[i+1]) { sum++; i++; } if(j>=typed.length())return false;//注意如果是typed里的字符串转化后的长度小于name的长度则肯定不符合题意 if(typed[j]!=name[i])return false; else { while(typed[j]==name[i]) { if(sum>0) sum--; j++; } if(sum>0) return false; } } if(j<typed.length()) return false;//判断typed的尾部是否还存在多余的字符 return true; } };