809.情感丰富的文字

链接：809.情感丰富的文字
难度：Medium
标签：数组、双指针、字符串
简介：输入一组查询单词，输出其中可扩张的单词数量。

题解 1 - cpp

• 编辑时间：2022-11-25
• 内存消耗：7.3MB
• 编程语言：cpp
• 解法介绍：双指针遍历。

class Solution {
public:
    typedef pair<int, char> Node;
    int expressiveWords(string s, vector<string>& words) {
        vector<Node> list;
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            int cnt = 1;
            while (i + 1 < s.size() && s[i + 1] == c) i++, cnt++;
            list.push_back(make_pair(cnt, c));
        }
        int ans = 0;
        for (auto &s : words) if (check(list, s)) ans++;
        return ans;
    }
    bool check(vector<Node> &list, string &s) {
        int cur = 0, i = 0;
        for (; i < s.size() && cur < list.size(); i++, cur++) {
            Node &node = list[cur];
            char c = s[i];
            int cnt = 1;
            while (i + 1 < s.size() && s[i + 1] == c) i++, cnt++;
            if (node.second != c ||
                node.first < cnt ||
                node.first == 2 && cnt == 1
            ) return false;
        }
        return i == s.size() && cur == list.size();
    }
};