ধরুন আমাদের একটি স্ট্রিং, s, এবং আমাদের কাছে শব্দের একটি তালিকাও রয়েছে, অ্যারেতে উপস্থিত শব্দগুলি একই দৈর্ঘ্যের। আমাদেরকে s-তে সাবস্ট্রিং(গুলি) এর সমস্ত প্রারম্ভিক সূচকগুলি খুঁজে বের করতে হবে যা শব্দের প্রতিটি শব্দের সংযোজন ঠিক একবার এবং কোনও হস্তক্ষেপকারী অক্ষর ছাড়াই৷
সুতরাং ইনপুট যদি হয় “barfoothefoobarman” এর মত এবং শব্দগুলো হয় [“foo”, “bar”], তাহলে আউটপুট হবে [0,9]। এর কারণ হল সূচক 0 এবং 9 থেকে শুরু হওয়া সাবস্ট্রিং হল "বারফু" এবং "ফুবার"।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ok() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি স্ট্রিং s, ম্যাপ wordCnt এবং n −
লাগবে -
s-এর একটি অনুলিপি temp এ তৈরি করুন
-
i এর জন্য n থেকে s - 1
এর পরিসরে-
যদি তাপমাত্রার আকার 0 এর একাধিক হয়, তাহলে
-
যদি wordCnt-এ temp উপস্থিত না থাকে, তাহলে মিথ্যা ফেরত দিন
-
অন্যথায়
-
যদি wordCnt[temp] 1 হয়, তাহলে wordCnt থেকে temp মুছে দিন, temp একটি খালি স্ট্রিং হিসাবে সেট করুন
-
অন্যথায় wordCnt[temp] এর মান 1 দ্বারা কমিয়ে দিন, temp খালি স্ট্রিং হিসাবে সেট করুন।
-
-
-
s[i>
দ্বারা তাপমাত্রা বাড়ান
-
-
যদি টেম্প wordCnt-এ না থাকে, তাহলে মিথ্যা ফেরত দিন
-
অন্যথায়
-
যদি wordCnt[temp] 1 হয়, তাহলে wordCnt থেকে temp মুছে ফেলুন, temp সেট করুন একটি emptystring হিসাবে
-
অন্যথায় wordCnt[temp] এর মান 1 দ্বারা কমিয়ে দিন, temp খালি স্ট্রিং হিসাবে সেট করুন।
-
-
wordCnt-এর আকার 0
হলে true রিটার্ন করুন -
মূল পদ্ধতি থেকে, এটি করুন
-
যদি a এর আকার 0 হয়, বা b এর আকার 0 হয়, তাহলে খালি অ্যারে ফেরত দিন
-
একটি মানচিত্র wordCnt তৈরি করুন, b-এ উপস্থিত স্ট্রিংগুলির ফ্রিকোয়েন্সি wordCnt
-এ সংরক্ষণ করুন -
ans
নামে একটি অ্যারে তৈরি করুন -
window :=শব্দের সংখ্যা x প্রতিটি শব্দে অক্ষরের সংখ্যা
-
স্ট্রিং-এর একটি কপি তৈরি করুন a in temp
-
i এর জন্য রেঞ্জ উইন্ডোতে a – 1
এর আকার-
যদি টেম্প সাইজ উইন্ডো দ্বারা বিভাজ্য হয় এবং ঠিক আছে (temp, wordCnt, b[0] এর আকার), তাহলে
-
ans
-এ i – উইন্ডো সন্নিবেশ করুন
-
-
temp
এ একটি [i] সন্নিবেশ করান -
যদি temp> উইন্ডোর আকার হয়, তাহলে 0, 1
থেকে সাবস্ট্রিং মুছে দিন
-
-
যদি টেম্প সাইজ উইন্ডো দ্বারা বিভাজ্য হয় এবং ঠিক আছে (temp, wordCnt, b[0] এর আকার), তাহলে
-
উত্তরের মধ্যে একটি – উইন্ডোর আকার সন্নিবেশ করুন
-
-
উত্তর ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> 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; } }; main(){ vector<string> v = {"foo", "bar"}; Solution ob; print_vector(ob.findSubstring("barfoothefoobarman", v)); }
ইনপুট
1,2,3,4,5,6,7 3
আউটপুট
[0, 9, ]