leetcode-792匹配子序列的单词数(桶)

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题链接

给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。

示例:

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

注意:

• 所有在words和 S 里的单词都只由小写字母组成。
• S 的长度在 [1, 50000]。
• words 的长度在 [1, 5000]。
• words[i]的长度在[1, 50]。

题解

1. 暴力

class Solution { 
   
public:
    int numMatchingSubseq(string s, vector<string>& words) { 
   
        int res = 0;
        for(auto &word : words){ 
   
            int j = 0,len = 0;
            for(int i = 0;i < s.size();i ++){ 
   
                if(word[j] == s[i])len ++,j ++;
            }
            if(len == word.size())res ++;
        }
        return res;
    }
};

2. 借鉴桶排序，把所有单词的字符按照word[0]放入对应桶，当字符串扫到对应字符的时候就把桶中的单词放入下一个字符对应的桶即可

class Solution { 
   
public:
    int numMatchingSubseq(string s, vector<string>& words) { 
   
        vector<pair<string,int> > v[26];
        int res = 0;
        for(auto &w : words){ 
   
            v[w[0] - 'a'].push_back({ 
   w,0});
        }
        for(int i = 0;i < s.size();i ++){ 
   
            int c = s[i] - 'a';
            vector<pair<string,int> > t = v[c];
            v[c].clear();
            for(auto &a : t){ 
   
                if(a.second == a.first.size() - 1)res ++;
                else v[a.first[a.second + 1] - 'a'].push_back({ 
   a.first,a.second + 1});
            }
        }
        return res;
    }
};