2020-10-21 第2题
题目来源：leetcode 每日一题
925. 长按键入
你的朋友正在使用键盘输入他的名字 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字符串出现顺序相同的两个字符就说明这一组成功，flag++（最后flag的值应该是name字符串的长度-1 ，如果想提高效率，可能加上一句，如果找不到直接退出会更快，一会儿试试----------------试完了，时空复杂度反倒下降了，不懂）。 写完以后报错了，因为两种情况没有考虑： 1、alex-alexxr（末尾多字符） 2、alex-ssalex（开头多字符） 我因为懒得想太多就直接加了两个判断，开头第一个字符必须和name[0]相同，结尾所有字符必须和name[name_len-1]相同。
class Solution { public: bool isLongPressedName(string name, string typed) { int name_len=name.size(); int typed_len=typed.size(); int flag=0,i,j,vernier=0; char ver_pre,ver_cur,tmp_cur,tmp_pre,tail; for(i=0;i<name_len-1;i++) { ver_pre=name[i]; ver_cur=name[i+1]; for(j=vernier;j<typed_len;j++) { tmp_pre=typed[j]; tmp_cur=typed[j+1]; if(tmp_pre==ver_pre&&tmp_cur==ver_cur) { flag++; vernier=j+1; break; } //else if(j+1==typed_len) //return false;（不知道为什么加了这个时空复杂度反倒下降了......） } } if(flag!=name_len-1) return false; else { //flag=0; tail=name[name_len-1]; for(i=vernier;i<typed_len;i++) { if(typed[i]!=tail) return false; } if(name[0]!=typed[0]) return false; return true; } } };运行结果如下，我其实不明白为什么运行第二遍效率涨了这么多，这到底是怎么算的？
一会儿吃饭回来看别人的题解。不过代码长度和运行时间好像没什么太大的关系。
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++; } } if(j==name.size()) return true; else return false; } }; 上方为空间复杂度最低的题解： name和typed从零开始遍历，当name字符串走完，或者typed中当前字符和name当前字符不匹配的时候进行判断，如果两个字符串第一个字符就不匹配那必然false，如果不是i==0，那就判断这个字符是不是长按造成的，如果不是，也false；如果name和typed的当前字符相同，那么就说明name中的字符有匹配，j++。最后看j和name的长度是否相等，相等就说明name中全部字符都有匹配。（那么alex-alexss这种它能判断吗？能，因为for循环的范围是typed整个的长度，其中的字符只有name匹配和长按两种来源，不符合的直接return false了）。－－－－－－－－－－－－－－－－－－－－－－－-－－－－－－－－－－－－－－－－
class Solution { public: void table(string name,vector<pair<char,int>>& v1) { for(int i = 0; i < name.size();i++) { if(v1.empty()) { pair<char,int> p; p.first = name[i]; p.second = 1; v1.push_back(p); } else { if(v1.back().first == name[i]) v1.back().second++; else { pair<char,int> p; p.first = name[i]; p.second = 1; v1.push_back(p); } } } } bool isLongPressedName(string name, string typed) { vector<pair<char,int>> v1; vector<pair<char,int>> v2; table(name,v1); table(typed,v2); if(v1.size() != v2.size()) return false; for(int i = 0; i < v1.size();i++) { if(v1[i].first != v2[i].first) return false; else if(v1[i].second > v2[i].second) return false; } return true; } };上方为空间复杂度最高的题解（看了几个答案，我还是不太明白这时空复杂度怎么定的，提交相同答案获得不同时空使用情况）： 我试图理解这个答案的题解思路，首先把name和typed中每个不同字符连续出现的个数用table函数进行数目统计，在主要判断函数中，首先判断两个用于统计的vector长度是否一致，不一致直接退出；如果字符出现的顺序不同（这个想法是我一开始的想法，我当时觉得写出来会麻烦，事实证明确实要用我不熟悉的pair和vector，统计每个字符顺序出现的次数），那直接false；如果字符出现顺序相同，就判断连续字符个数是否相同，如果name中的字符数>typed中的，那就说明typed不符合要求，直接退出；其余情况都符合要求。分析应该是数据结构用的比较多，所以空间复杂度较大。
