大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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]。
题解
- 暴力
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;
}
};
- 借鉴桶排序，把所有单词的字符按照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;
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168735.html原文链接：https://javaforall.net
