力扣工作周刷题 - 925. 长按键入

2020.10.21 原题：点击原题

一道有关字符串匹配的题，虽然写着简单难度，可是想了很久的边界条件，我太菜了。。

按照题意，必定得知一定是需要采用双指针（如果采用哈希表之类的数据结构，没有办法确认字符的顺序。） 并且可知，双指针对应有三种可能： 1、name【i】字符 == typed【j】字符 i和j一起增1； 2、上面条件不满足，但是typed【j】 == typed【j-1】 那么得知这里的字符是长按的，可以j++ 3、上面两个条件都不满足，返回false；

最后，如果 i == name的长度，说明刚好匹配，返回true；

时间复杂度：O（N+M） N为name字符串长度 M为typed字符串长度 空间复杂度：O（1）

java版本：

class Solution { public boolean isLongPressedName(String name, String typed) { if(name.length() == 0){ return true; } if(typed.length() == 0){ return false; } char[] L_ch = name.toCharArray(); char[] R_ch = typed.toCharArray(); int i = 0; int j = 0; while(j<R_ch.length){ if( i<L_ch.length && L_ch[i] == R_ch[j]){ i++; j++; continue; } if(j > 0 && R_ch[j] == R_ch[j-1]){ j++; continue; } return false; } if(i == L_ch.length){ return true; } return false; } }

C++版本

class Solution { public: bool isLongPressedName(string name, string typed) { if(name.length() == 0){ return true; } if(typed.length() == 0){ return false; } int i = 0; int j = 0; //因为typed的长度一般情况比原数组长 while(j < typed.length()){ if( i< name.length() && name[i] == typed[j]){ i++; j++; continue; } if( j>0 && typed[j] == typed[j-1]){ j++; continue; } return false; } return i == name.length(); } };