স্ট্রিং S এবং শব্দের লিস্ট words দেওয়া। words-এ কতটি শব্দ S-র সাবসিকোয়েন্স তা বের করতে হবে।
উদাহরণ: S="abcde", words=["a","bb","acd","ace"] → ৩ ("a","acd","ace")।
সমাধানের ধাপসমূহ
- প্রতিটি শব্দকে তার প্রথম ক্যারেক্টার অনুযায়ী বাকেটে বান্দর করুন (Map
- S-র প্রতিটি ক্যারেক্টার x এর জন্য: x-বাকেটের সব শব্দ প্রসেস করুন।
- শব্দের লেন্থ ১ হলে অ্যান্স++, অন্যথায় বাকি অংশ পরবর্তী ক্যারেক্টারের বাকেটে দিন।
- এইভাবে O(|S| + Σ|words|) টাইমে সমাধান।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numMatchingSubseq(string S, vector<string>& words) {
vector<vector<string>> buckets(26);
for (auto& w : words) buckets[w[0]-'a'].push_back(w);
int ans = 0;
for (char c : S) {
auto& bucket = buckets[c-'a'];
buckets[c-'a'].clear();
for (auto& w : bucket) {
if (w.size() == 1) ans++;
else buckets[w[1]-'a'].push_back(w.substr(1));
}
}
return ans;
}
};
int main() {
Solution ob;
string s = "abcde";
vector<string> v = {"a","bb","acd","ace"};
cout << ob.numMatchingSubseq(s, v);
}
ইনপুট
"abcde" ["a","bb","acd","ace"]
আউটপুট
3
