मान लीजिए हमारे पास एक स्ट्रिंग S और शब्दों का एक शब्दकोश words है, उन words[i] की संख्या ढूंढें जो S का उपअनुक्रम हैं। उदाहरण के लिए, यदि इनपुट 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]
- यदि x मैप m में मौजूद है, तो
- 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"]
आउटपुट
3
