資料結構
網路
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 個瀏覽量
廣告