C ++中的匹配子序列数
假设我们有一个字符串S和一个单词word的字典，请找到单词S的子序列[i]的数量。因此，如果输入为S=“abcde”，而字典为[“a”，“bb”，“acd”，“ace”]，则输出为3。因为字典中存在三个单词序列，它们是S的子序列：“a”，“acd”和“ace”
为了解决这个问题，我们将遵循以下步骤-
n：=单词数组的大小
创建一张映射
对于我来说，范围是0至字数
在映射的m[words[i，0]]位置插入words[i]
回答：=0
对于范围从0到S的i
temp：=m[x]，然后删除m[x]
对于范围在0到临时大小之间的j
如果temp[j]的大小=1，则将ans加1，否则将temp[j]的子字符串从索引1插入m[temp[j，1]]
字符x：=S[i]
如果在映射m中存在x，则
返回ans
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numMatchingSubseq(string S, vector<string>& words) {
int n = words.size();
map <char, vector <string> > m;
for(int i = 0; i < words.size(); i++){
m[words[i][0]].push_back(words[i]);
}
int ans = 0;
for(int i = 0; i < S.size(); i++){
char x = S[i];
if(m.find(x) != m.end()){
vector <string> temp = m[x];
m.erase(x);
for(int j = 0; j < temp.size(); j++){
if(temp[j].size() == 1){
ans++;
} else {
m[temp[j][1]].push_back(temp[j].substr(1));
}
}
}
}
return ans;
}
};
int main() {
Solution ob1;
string s = "abcde";
vector<string> v{"a","bb","acd","ace"};
cout << ob1.numMatchingSubseq(s, v) << endl;
return 0;
}输入值
"abcde"
["a","bb","acd","ace"]
string s = "abcde";
vector<string> v{"a","bb","acd","ace"};输出结果
3