力扣(LeetCode)809. 情感丰富的文字(C++)

模拟

分析单词可扩张条件 :
对于某个字母，设目标字母长度 $c1$ ，待扩张字母长度 $c2$
当 $c1<c2$，目标字母比待扩张字母少，false
当 $c1\ge c2$，目标字母比待扩张字母多或者相等，如果 $c1\ge 3$ 可以扩张。如果 $c1<3$ ，仅当 $c2=c1$ ，字母数量相等，等价于“可扩张”。

算法流程：

1. $s$ 判空，若空，统计 $words$ 里的空串
2. 统计 $s$ 中的字母组，依次存相邻字母和出现次数，保存在数组 $p$
3. 遍历 $words$ 中每个 $word$ ，如果 $p$ 先被遍历完，说明 $word$ 比 $s$ 长，不可扩张，break。如果当前字母不同，break。遍历 $word$ 当前字母长度 $c2$ ，比较 $c1$ 和 $c2$ 。
4. 仅当 $word$ 和 $p$ 同时遍历完，可扩张。

class Solution {
public:
    int expressiveWords(string s, vector<string>& words) {
        int ans = 0;
        if(s.empty()){
            for(auto &w:words) 
                if(w.empty()) ans++;
            return ans;
        }
        vector<pair<char,int>> p;
        for(int i = 0;i<s.size();i++){
            int j = i + 1;
            while(j<s.size()&&s[i]==s[j]) j++;
            p.push_back({s[i],j-i});
            i = j-1;
        }
        for(auto &w:words){
            int k = 0;//k指向p
            for(int i = 0 ;i<w.size();i++){//i指向w
                if(p.size()==k) {//p遍历完，w还没遍历完
                    k= -1;
                    break;
                }
                if(w[i]!=p[k].first) break;
                int j = i + 1;
                while(j<w.size()&&w[i]==w[j]) j++;
                int c1 = p[k].second, c2 = j - i;
                if(c1<c2) break;
                if(c1<3&&c1!=c2) break;
                k++,i = j - 1;
            }
            if(p.size()==k) ans++;//w和p同时遍历完
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

时间复杂度 $O(m+{\sum }_{i=0}^{n-1}word{s}_i)$ ，$n$ 是单词数量，$m$ 是待扩张字符串的长度。遍历每个单词的时间复杂度 $O({\sum }_{i=0}^{n-1}word{s}_i)$ ，遍历 $s$ 的时间复杂度 $O(m)$ ，总时间复杂度$O(m+{\sum }_{i=0}^{n-1}word{s}_i)$。

空间复杂度 $O(m)$ ，保存 $s$ 的字母组的最坏空间复杂度 $O(m)$ 。

致语

理解思路很重要。
欢迎读者在评论区留言，答主看到就会回复的。

AC