LeetCode 792. 匹配子序列的单词数 - 优化代码解析

LeetCode 792. 匹配子序列的单词数 - 优化代码解析

题目描述:

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

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

例如，'ace' 是 'abcde' 的子序列。

原始代码:

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        int num = 0;
        //s = "abcde", words = ["a","bb","acd","ace"]
        for (int i = 0; i < words.size(); i++) {
            string s1 = s;
            int n = 0;
            for (int j = 0; j < words[i].size(); i++) { // 错误：索引 i 应该为 j
                auto it = s1.find(words[i][j]);
                if (it == string::npos)
                    continue;
                n++;
                swap(s1[s1.size() - 1], s1[it]);
			    s1=s1.erase(s1.size() - n);
                if (j == words[i].size() - 1)
                    num++;
            }

        }
        return num;  
    }
};

代码优化：

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        int num = 0;
        for (int i = 0; i < words.size(); i++) {
            string s1 = s;
            int n = 0;
            for (int j = 0; j < words[i].size(); j++) { // 修改：索引 i 改为 j
                auto it = s1.find(words[i][j]);
                if (it == string::npos)
                    continue;
                n++;
                swap(s1[s1.size() - 1], s1[it]);
                s1 = s1.erase(s1.size() - n);
                if (j == words[i].size() - 1)
                    num++;
            }
        }
        return num;  
    }
};

代码解释：

1. 外层循环遍历 words 数组，检查每个单词是否为 s 的子序列。
2. 内层循环遍历每个单词的字符，使用 find() 函数在 s 中查找当前字符。
3. 如果字符在 s 中存在，则将 s 中该字符与 s 的最后一个字符交换位置，并删除 s 的最后一个字符。
4. 如果内层循环遍历完毕，则表示该单词是 s 的子序列，计数器 num 加 1。

错误分析：

原始代码中的错误在于内层循环的索引使用的是 i，而不是 j。应该使用 j 来遍历当前单词的字符，而不是使用 i 来遍历 words 数组。

总结：

本文提供 LeetCode 792 题（匹配子序列的单词数）的 C++ 代码实现，并对代码进行了优化，解释了代码逻辑，并针对常见错误进行了分析。希望本文可以帮助您更好地理解该算法。