假设我们有一个字符串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