• 每日一题 —— LC. 792 匹配子序列的单词数

    特此记录！注意以后用C++写题时，能用引用就尽量用引用！

    特此记录！注意以后用C++写题时，能用引用就尽量用引用！

    特此记录！注意以后用C++写题时，能用引用就尽量用引用！

    792. 匹配子序列的单词数

    给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。

    字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。

    例如， “ace” 是 “abcde” 的子序列。

    提示

    • 1 <= s.length <= 5 * 10^4
    • 1 <= words.length <= 5000
    • 1 <= words[i].length <= 50
    • words[i]和 s 都只由小写字母组成。

    示例

    输入: s = "abcde", words = ["a","bb","acd","ace"]
输出: 3
解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。

    • 1
    • 2
    • 3

    思路

    假设待匹配的单词里面有一个字母a，那么我们需要在主串s中找到一个字母a来与之匹配，如果s中存在多个a，那么我们用哪个来匹配呢？答案是最左侧的a，即最早出现的那一个。

    因为选择越靠左侧的a，能让其右侧的字母尽可能的多。对于待匹配单词中字母a的下一个字母，假设是b，我们需要从s中，我们选择的字母a后面，再找到一个b来与之匹配。选择最靠左的a，能让其右侧可供选择的字母数量最多，就越有可能匹配到字母b。

    举个简单的例子，加入s = cabcade，待匹配单词w = ac，

    我们匹配时，先取w的第一个字母，即a，然后尝试在s中找到一个a来与之匹配，而此时s中有2个a，我们应当取哪个呢？当然应该取最左侧的那个。因为这样能让s中右侧剩余部分最长，剩余部分的字母也就越多，就越有可能匹配上w后续的字母。同时需要注意，当我们匹配了第一个a后，在匹配w的第二个字母c时，必须要求s中选择的c，一定要在s中选择的a的右侧。从上面的例子来说，就是我们不能选择s中的第一个c，因为其不在a的右侧。

    于是我们的思路就比较清晰了。我们依次遍历待匹配单词w的每个字符，对于当前字符c，每次尝试在主串s中查找这个字符，但是需要注意，查找的c的下标，必须要大于前一个匹配的字符在s中的位置。

    即，对于w中每个字符c，我们需要维护一个左边界left，我们在主串s中，查找下标大于left的第一次字符c，设其下标为idx，找到后，我们更新left = idx，此时的left是作为下一个待匹配字符的左边界。

    只要对于w中的每个字符，我们都能在s中完成匹配。那么该w就是s的一个子序列。

    要完成上述操作，我们需要先遍历一次主串s，将每个字符出现的位置保存下来（某个字符出现多次的话，就保存多个下标）。而每次我们查找字符时，直接取该字符在s中出现的下标数组，并通过二分，查找到第一个大于left的下标即可。

    // C++ 144ms
class Solution {
public:

    // 在idx中找到第一个大于left的位置
    int find(vector<int>& idx, int left) {
        // idx可能为空
        if (idx.size() == 0) return -1;
        int l = 0, r = idx.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (idx[mid] > left) r = mid;
            else l = mid + 1;
        }
        if (idx[l] > left) return idx[l];
        return -1;
    }

    int numMatchingSubseq(string s, vector<string>& words) {
        // 由于全是小写字母, 可以直接开一个大小为26的vector
        vector<vector<int>> idx(26);
        // 保存每个字符出现的下标
        for (int i = 0; i < s.size(); i++) {
            idx[s[i] - 'a'].push_back(i);
        }
        int ans = 0;
        for (auto& w : words) {
            int l = -1;
            bool yes = true;
            for (int i = 0; i < w.size(); i++) {
                vector<int>& v = idx[w[i] - 'a']; // 注意这里要加引用 & , 否则会超时
                // 不加引用的话每次取都会拷贝一次, 会非常消耗性能
                l = find(v, l); // 这里可以直接用 upper_bound 函数替代
                if (l == -1) {
                    yes = false;
                    break;
                }
            }
            if (yes) ans++;
        }
        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
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    也可以用STL中的upper_bound函数来替代自实现的二分查找

    // C++ 144ms
class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        // 由于全是小写字母, 可以直接开一个大小为26的vector
        vector<vector<int>> idx(26);
        // 保存每个字符出现的下标
        for (int i = 0; i < s.size(); i++) {
            idx[s[i] - 'a'].push_back(i);
        }
        int ans = 0;
        for (auto& w : words) {
            int l = -1;
            bool yes = true;
            for (int i = 0; i < w.size(); i++) {
                vector<int>& v = idx[w[i] - 'a']; // 注意这里要加引用 & , 否则会超时
                // 不加引用的话每次取都会拷贝一次, 会非常消耗性能
                vector<int>::iterator it = upper_bound(v.begin(), v.end(), l);
                // upper_bound是查找第一个 > 某个数的
                // lower_bound是查找第一个 >= 某个数的
                if (it == v.end()) {
                    // 没找着
                    yes = false;
                    break;
                }
                l = *it; //找着了, 更新left边界
            }
            if (yes) ans++;
        }
        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

    今早做这道题时，我自己想出了二分的做法，但是提交一直TLE。最后针对几个样例数据，加了set做缓存+去重，以及对一些情况加了些特判，才勉强通过。

    image-20221117102733637

    非常艰难的AC！！下面是我TLE的代码

    class Solution {
public:

    // 在idx中找到第一个大于left的位置
    int find(vector<int>& idx, int left) {
        int l = 0, r = idx.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (idx[mid] > left) r = mid;
            else l = mid + 1;
        }
        if (idx[l] > left) return idx[l];
        return -1;
    }

    // 4 × 10^6
    int numMatchingSubseq(string s, vector<string>& words) {
        // 只包含小写字母, 可以存储一下每个字母第一次出现时的位置, 哈哈哈
        unordered_map<int, vector<int>> idx;
        for (int i = 0; i < s.size(); i++) {
            int u = s[i] - 'a';
            idx[u].push_back(i);
        }
        // for (auto& [k, v] : idx) {
        //     char c = k + 'a';
        //     printf("char = %c : -> ", c);
        //     for (auto& i : v) printf("%d, ", i);
        //     printf("\n");
        // }

        int ans = 0;
        for (auto& w : words) {
            // printf("word = %s, ", w.c_str());
            int cnt = 0, l = -1;
            for (int i = 0; i < w.size(); i++) {
                int u = w[i] - 'a';
                if (idx.find(u) == idx.end()) break;
                vector<int> v = idx.find(u)->second;
                l = find(v, l);
                // printf("char = %c, idx = %d; ", w[i], l);
                if (l == -1) break; // 没找着
                cnt++;
            }
            if (cnt == w.size()) {
                // printf("yes!");
                ans++;
            }
            // printf("\n");
        }
        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
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    可以看到我加了很多print进行反复调试。下面是我加了set做缓存，加了一些特判后勉强AC的代码。

    // C++ 1248ms
class Solution {
public:

    // 在idx中找到第一个大于left的位置
    int find(vector<int>& idx, int left) {
        int l = 0, r = idx.size() - 1;
        while (l < r) {
            // printf("%d次二分", c);
            if (left == -1) break; // 第一次, 直接break, 取l = 0
            int mid = l + r >> 1;
            if (idx[mid] > left) r = mid;
            else l = mid + 1;
        }
        if (idx[l] > left) return idx[l];
        return -1;
    }

    // 4 × 10^6
    int numMatchingSubseq(string s, vector<string>& words) {
        // 只包含小写字母, 可以存储一下每个字母第一次出现时的位置, 哈哈哈
        unordered_map<char, vector<int>> idx;
        for (int i = 0; i < s.size(); i++) {
            idx[s[i]].push_back(i);
        }
        // for (auto& [k, v] : idx) {
        //     printf("char = %c : -> ", k);
        //     for (auto& i : v) printf("%d, ", i);
        //     printf("\n");
        // }
        // 缓存已判断过的单词
        unordered_set<string> valid;
        unordered_set<string> invalid;
        int ans = 0;
        for (auto& w : words) {
            if (valid.count(w)) {
                ans++;
                continue;
            }
            if (invalid.count(w)) continue;
            // printf("word = %s, ", w.c_str());
            int cnt = 0, l = -1;
            for (int i = 0; i < w.size(); i++) {
                char u = w[i];
                if (idx.find(u) == idx.end()) break;
                vector<int> v = idx.find(u)->second;
                l = find(v, l);
                // printf("char = %c, idx = %d; ", w[i], l);
                if (l == -1) break; // 没找着
                cnt++;
            }
            if (cnt == w.size()) {
                // printf("yes!");
                ans++;
                valid.emplace(w);
            } else {
                invalid.emplace(w);
            }
            // printf("\n");
        }
        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
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    后来看题解，发现别人的思路和我的一样，但是用别人的代码提交，就运行非常快。我非常纳闷，一行一行代码的进行对比，删除调试。

    最后发现，是因为我后面取vector时，没有加引用导致的！

    然后我把上面那份TLE的代码，只多加了一个引用符号 &，就AC了，跑了180ms

    就是这句

    vector<int> v = idx.find(u)->second;

    • 1

    多加了引用符号，改成了

    vector& v = idx.find(u)->second;

    • 1

    C++中如果不加&，会默认进行数据拷贝，所以会非常吃性能！

    下次一定要注意，从容器中取数据时，尽可能的使用引用！

    但同时也要注意，使用引用取出的数据，修改就是直接在原数据上修改！而不是在数据的副本上修改。

  • 相关阅读:
    Mac M1安装ROS1或ROS2
    python数据分析—删除value=0的行
    计算机毕业设计Java民宿短租交易平台(源代码+数据库+系统+lw文档)
    vscode编辑器创建分支注意事项？！
    JavaScript之BOM与DOM操作
    cnpm的安装与使用
    smt加工企业多不多？如何进行了解？
    k8s1.19使用ceph14
    微信小程序——生命周期详解（代码解读）
    【React】面试题5题
  • 原文地址：https://blog.csdn.net/vcj1009784814/article/details/127899316