给定字符串 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：Map
解题思路
1.根据words数组每个字符串的首字母将其在数组内的索引值存入到首字母对应的map中，例如words[3]=”bacc” 则 map[‘b’]=[3];（map类型为<char,vector>）
2.遍历S数组，若当前位置的字符在map中有值，将其map的值提出赋值给t数组，并将原来map值清空
3.构建wordnum数组，用来存当前情况下，各个words已经匹配到的字符数。遍历t数组，提出每个索引，判断该索引words单词是否已经匹配完全，若未完全，根据其下一个字符放入对应map中
4.遍历wordnum数组，若wordnum[i]>=words[i].size()表示该单词匹配成功，res+1
5.返回res
改进：
1.发现其中有很多重复单词，利用map统计各个不同单词出现的次数，将没有重复单词的字符串赋值给words
更新新的words个数
2.统计res时，根据该单词出现的次数更新
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
| class Solution {
public:
int numMatchingSubseq(string S, vector<string>& words) {
int wordlen=words.size();
int i;
unordered_map<char,vector<int>> m;
unordered_map<string,int> mset;
for(i=0;i<wordlen;i++)
{
mset[words[i]]++;
}
i=0;
for(auto iter = mset.begin(); iter != mset.end(); ++iter)
{
words[i]=iter->first;
i++;
}
wordlen=i;
vector<int> wordnum(wordlen,0);
for(i=0;i<wordlen;i++)
{
m[words[i][0]].push_back(i);
}
for(i=0;i<S.length();i++)
{
vector<int> t(m[S[i]]);
int j;
m[S[i]].clear();
for(j=0;j<t.size();j++)
{
int k=t[j];
wordnum[k]++;
if(wordnum[k]<words[k].size())
{
m[words[k][wordnum[k]]].push_back(k);
}
}
}
int res=0;
for(i=0;i<wordlen;i++)
{
if(wordnum[i]>=words[i].size())
{
res+=mset[words[i]];
}
}
return res;
}
};
|