मान लीजिए हमारे पास शब्दों की एक सूची है। ये शब्द विशिष्ट हैं। हमें एक एल्गोरिदम तैयार करना है जो दी गई शब्दों की सूची में सभी संयोजित शब्दों को ढूंढेगा। एक संयोजित शब्द वास्तव में एक स्ट्रिंग है जो दिए गए सरणी में कम से कम दो छोटे शब्दों से पूरी तरह से बना है।
तो यदि शब्द ["cow", "cows", "cowsgoatcows", "goat", "goatcowsgoat", "hippopotamuses", "deer", "deercowgoatcow"] जैसे हैं, तो आउटपुट ["cowsgoatcows", "goatcowsgoat", "deercowgoatcow"] होगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- एक फ़ंक्शन isPresent() परिभाषित करें, जो str, head, idx, एक सरणी dp लेगा,
- यदि idx >= str का आकार, तो -
- true लौटाएं
- यदि dp[idx] -1 के बराबर नहीं है, तो -
- dp[idx] लौटाएं
- एक नोड curr := head बनाएं
- ok := false
- i := idx से आरंभ करें, जब i < str का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें -
- x := str[i]
- यदि curr का child[x] नहीं है, तो -
- लूप से बाहर आएं
- अन्यथा
- curr := curr का child[x]
- यदि curr का isEnd सत्य है, तो -
- ok := ok OR isPresent(str, head, i + 1, dp)
- dp[idx] := ok लौटाएं
- एक फ़ंक्शन insertNode() परिभाषित करें, जो head, s लेगा,
- एक नोड curr = head बनाएं
- i := 0 से आरंभ करें, जब i < s का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें -
- x := s[i]
- यदि curr का child[x] नहीं है, तो -
- curr का child[x] := एक नया Node बनाएं
- curr := curr का child[x]
- curr का isEnd := true
- मुख्य विधि से, निम्नलिखित करें -
- head := एक नया Node बनाएं
- शब्दों की लंबाई के आधार पर सरणी words को सॉर्ट करें
- एक सरणी ret परिभाषित करें
- i := 0 से आरंभ करें, जब i < words का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें -
- curr := words[i]
- यदि curr "" के समान है, तो -
- निम्न भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
- curr के समान आकार की एक सरणी dp परिभाषित करें, इसे -1 से भरें
- यदि isPresent(curr, head, 0, dp) को कॉल करना शून्येतर है, तो -
- curr को ret के अंत में डालें
- अन्यथा
- फ़ंक्शन insertNode(head, curr) को कॉल करें
- ret लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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; } struct Node{ bool isEnd; map <char, Node*> child; Node(){ isEnd = false; } }; class Solution { public: bool isPresent(string str, Node* head, int idx, vector <int>& dp){ if(idx >= str.size())return true; if(dp[idx] != -1)return dp[idx]; Node* curr = head; bool ok = false; for(int i = idx; i < str.size(); i++){ char x = str[i]; if(!curr->child[x]){ break; }else{ curr = curr->child[x]; } if(curr->isEnd){ ok |= isPresent(str, head, i + 1, dp); } } return dp[idx] = ok; } static bool cmp(string s1, string s2){ return s1.size() < s2.size(); } void insertNode(Node* head, string s){ Node* curr = head; for(int i = 0; i < s.size(); i++){ char x = s[i]; if(!curr->child[x]){ curr->child[x] = new Node(); } curr = curr->child[x]; } curr->isEnd = true; } vector<string> findAllConcatenatedWordsInADict(vector<string>& words) { Node* head = new Node(); sort(words.begin(), words.end(), cmp); vector <string> ret; for(int i = 0; i < words.size(); i++){ string curr = words[i]; if(curr=="")continue; vector <int> dp(curr.size(), -1); if(isPresent(curr, head, 0, dp)){ ret.push_back(curr); }else{ insertNode(head, curr); } } return ret; } }; main(){ Solution ob; vector<string> v = {"cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"}; print_vector(ob.findAllConcatenatedWordsInADict(v)); }इनपुट
{"cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"}आउटपुट
[cowsgoatcows, goatcowsgoat, deercowgoatcow, ]
