ধরুন আমাদের কাছে একটি স্ট্রিং s এবং শব্দের একটি লিস্ট words আছে, যেখানে সব শব্দের দৈর্ঘ্য সমান। আমাদের কাজ হল s-এ تلك সাবস্ট্রিংয়ের শুরুর ইনডেক্সগুলো খুঁজে বের করা যা words অ্যারেতে থাকা প্রতিটি শব্দকে ঠিক একবার করে এবং কোনো হস্তক্ষেপকারী অক্ষর ছাড়া ক্যাটিনেট (concatenation) করে তৈরি।
যেমন, s = "barfoothefoobarman" এবং words = ["foo", "bar"] হলে আউটপুট হবে [0, 9]। কারণ ইনডেক্স ০ এবং ৯ থেকে শুরু হওয়া সাবস্ট্রিংগুলো হল "barfoo" এবং "foobar"।
সমাধানের ধাপসমূহ:
ok() নামে একটি মেথড সংজ্ঞায়িত করুন যা s, wordCnt ম্যাপ এবং n গ্রহণ করবে
s-কে temp-এ কপি করুন
i = n থেকে s.size()-1 পর্যন্ত লুপ: যদি temp.size() n-এর গুণিতক হয়, তবে wordCnt-এ temp আছে কিনা চেক করুন, থাকলে ফ্রিকোয়েন্সি কমান বা মুছে দিন, temp খালি করুন। temp-এ s[i] যোগ করুন।
শেষে temp wordCnt-এ আছে কিনা চেক করে একই কাজ করুন। wordCnt.size() == 0 হলে true রিটার্ন করুন।
মূল ফাংশন থেকে: যদি a বা b খালি হয় তবে খালি অ্যারে রিটার্ন করুন। wordCnt-এ b-এর শব্দগুলোর ফ্রিকোয়েন্সি রাখুন। window := words.size() * words[0].size()। a-এর প্রথম window অক্ষর temp-এ রাখুন। i = window থেকে a.size()-1 পর্যন্ত লুপ: যদি temp.size() window দ্বারা বিভাজ্য হয় এবং ok() true রিটার্ন করে, তবে i-window ans-এ যোগ করুন। temp-এ a[i] যোগ করুন, যদি temp.size() > window হয় তবে প্রথম অক্ষর মুছে দিন। শেষে একবার আর চেক করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v) {
cout << "[";
for(int i = 0; i < v.size(); i++) cout << v[i] << ", ";
cout << "]" << endl;
}
class Solution {
public:
bool ok(string s, unordered_map<string, int> wordCnt, int n) {
string temp = "";
for(int i = 0; i < n; i++) temp += s[i];
for(int i = n; i < s.size(); i++) {
if(temp.size() % n == 0) {
if(wordCnt.find(temp) == wordCnt.end()) return false;
else {
if(wordCnt[temp] == 1) { wordCnt.erase(temp); temp = ""; }
else { wordCnt[temp]--; temp = ""; }
}
}
temp += s[i];
}
if(wordCnt.find(temp) == wordCnt.end()) return false;
else {
if(wordCnt[temp] == 1) { wordCnt.erase(temp); temp = ""; }
else { wordCnt[temp]--; temp = ""; }
}
return wordCnt.size() == 0;
}
vector<int> findSubstring(string a, vector<string> &b) {
if(a.size() == 0 || b.size() == 0) return {};
unordered_map<string, int> wordCnt;
for(int i = 0; i < b.size(); i++) wordCnt[b[i]]++;
vector<int> ans;
int window = b.size() * b[0].size();
string temp = "";
for(int i = 0; i < window; i++) temp += a[i];
for(int i = window; i < a.size(); i++) {
if(temp.size() % window == 0 && ok(temp, wordCnt, b[0].size()))
ans.push_back(i - window);
temp += a[i];
if(temp.size() > window) temp.erase(0, 1);
}
if(temp.size() % window == 0 && ok(temp, wordCnt, b[0].size()))
ans.push_back(a.size() - window);
return ans;
}
};
int main() {
vector<string> v = {"foo", "bar"};
Solution ob;
print_vector(ob.findSubstring("barfoothefoobarman", v));
return 0;
}
ইনপুট
"barfoothefoobarman" ["foo", "bar"]
আউটপুট
[0, 9]
