สมมติว่าเรามีสตริง S และพจนานุกรมของคำ ค้นหาจำนวนคำ[i] ที่เป็นผลสืบเนื่องของ S ดังนั้นหากอินพุตคือ S=“abcde” และพจนานุกรมคือ [“a”, “bb” “acd”, “ace”] แล้วเอาท์พุตจะเป็น 3 เนื่องจากมีคำสามลำดับในพจนานุกรม ซึ่งเป็นลำดับรองของ S:“a” “acd” และ “ace”
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของอาร์เรย์คำ
- สร้างหนึ่งแผนที่ m
- สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของคำ
- แทรกคำ[i] ลงในแผนที่ m[words[i, 0]] ตำแหน่ง
- ตอบ :=0
- สำหรับ i ในช่วง 0 ถึงขนาด S
- ถ่าน x :=S[i]
- ถ้ามี x ในแผนที่ m แล้ว
- อุณหภูมิ :=m[x] และลบ m[x]
- สำหรับ j ในช่วง 0 ถึงขนาดอุณหภูมิ
- ถ้าขนาดของ temp[j] =1 ให้เพิ่ม ans ขึ้น 1 มิฉะนั้น ให้แทรกสตริงย่อยของ temp[j] จากดัชนี 1 ลงใน m[temp[j, 1]]
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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
