मान लीजिए हमारे पास एक स्ट्रिंग s है, और हमारे पास शब्दों की एक सूची भी है, ऐरे में मौजूद सभी शब्द समान लंबाई के हैं। हमें s में उन सभी सबस्ट्रिंग के प्रारंभिक इंडेक्स ढूंढने हैं जो words में प्रत्येक शब्द का ठीक एक बार संयोजन है और बिना किसी हस्तक्षेप वाले वर्णों के।
तो यदि इनपुट "barfoothefoobarman" जैसा है और शब्द ["foo", "bar"] हैं, तो आउटपुट [0,9] होगा। ऐसा इसलिए क्योंकि इंडेक्स 0 और 9 से शुरू होने वाले सबस्ट्रिंग "barfoo" और "foobar" हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
ok() नामक एक विधि परिभाषित करें, जो स्ट्रिंग s, मैप wordCnt और n लेगा −
s की एक प्रति temp में बनाएं
i को n से s के आकार - 1 तक की रेंज में
यदि temp का आकार 0 का गुणक है, तो
यदि temp wordCnt में मौजूद नहीं है, तो false लौटाएं
अन्यथा
यदि wordCnt[temp] 1 है, तो temp को wordCnt से हटाएं, temp को खाली स्ट्रिंग सेट करें
अन्यथा wordCnt[temp] के मान को 1 से घटाएं, temp को खाली स्ट्रिंग सेट करें।
temp को s[i] से बढ़ाएं
यदि temp wordCnt में नहीं है, तो false लौटाएं
अन्यथा
यदि wordCnt[temp] 1 है, तो temp को wordCnt से हटाएं, temp को खाली स्ट्रिंग सेट करें
अन्यथा wordCnt[temp] के मान को 1 से घटाएं, temp को खाली स्ट्रिंग सेट करें।
true लौटाएं जब wordCnt का आकार 0 हो
मुख्य विधि से, यह करें
यदि a का आकार 0 है, या b का आकार 0 है, तो खाली ऐरे लौटाएं
wordCnt नामक एक मैप बनाएं, b में मौजूद स्ट्रिंग्स की आवृत्ति को wordCnt में स्टोर करें
ans नामक एक ऐरे बनाएं
window := शब्दों की संख्या x प्रत्येक शब्द में वर्णों की संख्या
स्ट्रिंग a की एक प्रति temp में बनाएं
i को window से a के आकार - 1 तक की रेंज में
यदि temp का आकार window से विभाज्य है और ok(temp, wordCnt, b[0] का आकार) कॉल करें, तो
i - window को ans में डालें
a[i] को temp में डालें
यदि temp का आकार > window है, तो 0, 1 से सबस्ट्रिंग हटाएं
यदि temp का आकार window से विभाज्य है और ok(temp, wordCnt, b[0] का आकार) कॉल करें, तो
a के आकार - window को ans में डालें
ans लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
#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)); }इनपुट
"barfoothefoobarman", ["foo", "bar"]
आउटपुट
[0, 9, ]