数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 中匹配子序列的数量
假设我们有一个字符串 S 和一个单词字典 words，找到作为 S 子序列的单词 words[i] 数量。因此，如果输入是 S= “abcde”，且字典是 [“a”， “bb”， “acd”， “ace”]，则输出将为 3。因为字典中包含三个单词序列，它们是 S 的子序列：“a” “acd”和“ace”
要解决这个问题，我们将遵循以下步骤：
- n := words 数组的大小
- 创建一个映射 m
- 对于 i 在 0 到 words 大小范围内
- 将 words[i] 插入到映射 m[words[i, 0]] 位置
- ans := 0
- 对于 i 在 0 到 S 大小范围内
- char x := S[i]
- 如果 m 中存在 x，则
- temp := m[x]，并删除 m[x]
- 对于 j 在 0 到 temp 大小范围内
- 如果 temp[j] 的大小 = 1，则将 ans 增加 1，否则将 temp[j] 中从索引 1 开始的子字符串插入到 m[temp[j, 1]] 中
- 返回 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
更新于：30-4 月-2020
248 个浏览量
广告