C++ में स्ट्रिंग (S) में उन सबस्ट्रिंग्स के प्रारंभिक इंडेक्स खोजें जो लिस्ट (L) के सभी शब्दों को जोड़कर बनी हैं

मान लीजिए हमारे पास एक स्ट्रिंग s है, और हमारे पास कुछ शब्दों की एक लिस्ट है, ये शब्द समान लंबाई के हैं। हमें s में उन सभी सबस्ट्रिंग्स के प्रारंभिक इंडेक्स खोजने हैं जो लिस्ट के प्रत्येक शब्द को ठीक एक बार और बिना किसी मध्यवर्ती वर्णों के जोड़कर बनी हैं।

उदाहरण के लिए, यदि इनपुट "wordgoodgoodgoodword" है और शब्द ["word","good"] हैं, तो आउटपुट [0,12] होगा। ऐसा इसलिए क्योंकि इंडेक्स 0 और 12 से शुरू होने वाली सबस्ट्रिंग्स "wordgood" और "goodword" हैं।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

• ok() नामक एक मेथड परिभाषित करें, जो स्ट्रिंग s, मैप wordCnt और n लेता है
• s की एक कॉपी temp में बनाएं
• i को n से s के आकार - 1 तक रेंज में लूप करें
  • यदि temp का आकार n का गुणक है, तो
    • यदि 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 को खाली स्ट्रिंग सेट करें
• यदि wordCnt का आकार 0 है तो true लौटाएं
• मेन मेथड से, निम्न करें:
  • यदि a का आकार 0 है, या b का आकार 0 है, तो खाली ऐरे लौटाएं
  • wordCnt नामक एक मैप बनाएं, b में मौजूद स्ट्रिंग्स की फ्रीक्वेंसी wordCnt में स्टोर करें
  • ans नामक एक ऐरे बनाएं
  • विंडो := शब्दों की संख्या x प्रत्येक शब्द में वर्णों की संख्या
  • स्ट्रिंग a की एक कॉपी temp में बनाएं
  • i को 0 से विंडो-1 तक रेंज में लूप करें: temp में a[i] जोड़ें
  • i को विंडो से a के आकार - 1 तक लूप करें:
    • यदि temp का आकार विंडो से विभाज्य है और ok(temp, wordCnt, b[0] का आकार) कॉल करें, तो i - विंडो को ans में डालें
    • temp में a[i] जोड़ें
    • यदि temp का आकार > विंडो है, तो सबस्ट्रिंग 0, 1 से हटाएं
  • यदि temp का आकार विंडो से विभाज्य है और ok(temp, wordCnt, b[0] का आकार), तो a के आकार - विंडो को ans में डालें
  • ans लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

#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 = {"word","good"}; Solution ob; print_vector(ob.findSubstring("wordgoodgoodgoodword", v)); }

इनपुट

"wordgoodgoodgoodword", {"word","good"}

आउटपुट

[0, 12, ]