925.长按键入

题面

你的朋友正在使用键盘输入他的名字name。偶尔，在键入字符c时，按键可能会被长按，而字符可能被输入 1 次或多次。
你将会检查键盘输入的字符typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回True。

解析

输入name时，有若干个字符可能被重复输入多次，输入后的字符串为typed。判断当前typed是否是可能name的输入。

性质：

1.两个字符串unique后应当相同。
2.name应当为typed的子序列（非连续）。

算法

算法一：

采用性质1，对于两个字符串unique后应当相同，同时unique之前，每段相同的字母，typed中的长度应当大于等于name中的长度

算法二：

采用性质2，O(n)单指针扫一遍判断name是否为typed的子序列（从左往右），将name与typed中的字符一一对应，之后typed中多余的字符，都应当与其左边的字符相同

代码

算法一：

时间复杂度O(n)，额外空间复杂度O(n)。
c++，0ms

class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        int l = 0;
        vector<int>vname, vtyped;
        #统计每段相同字母的长度
        for(int i = 1;i < name.size();i++)
            if(name[i] != name[i-1]){
                vname.push_back(i-l);
                l = i;
                }
        vname.push_back(name.size()-l);
        l = 0;
        for(int i = 1;i < typed.size();i++)
            if(typed[i] != typed[i-1]){
                vtyped.push_back(i-l);
                l = i;
                }
        #unique字符串
        vtyped.push_back(typed.size()-l);
        name.erase(unique(name.begin(), name.end()),name.end());
        typed.erase(unique(typed.begin(), typed.end()),typed.end());
        cout<<name<<endl;
        cout<<typed<<endl;
        if(name!=typed)
            return false;
        if(vname.size()!=vtyped.size())
            return false;
        for(int i = 0 ;i < vname.size();i++)
            if(vname[i]>vtyped[i])
                return false;
        return true;
        
    }
};