सी ++ में वर्ड स्क्वायर

मान लीजिए कि हमारे पास शब्दों का एक सेट है (सभी अद्वितीय हैं), हमें सभी शब्द वर्ग खोजने होंगे और हम उनसे निर्माण कर सकते हैं। यहाँ शब्दों का एक क्रम एक मान्य शब्द वर्ग बनाता है यदि kth पंक्ति और स्तंभ ठीक उसी स्ट्रिंग को पढ़ते हैं, जहाँ 0 k <अधिकतम संख्याएँ और numColumns। तो एक उदाहरण के रूप में, शब्द क्रम ["बॉल", "एरिया", "लीड", "लेडी"] एक शब्द वर्ग का निर्माण करेगा क्योंकि प्रत्येक शब्द क्षैतिज और लंबवत दोनों तरह से समान पढ़ता है।

इसलिए, यदि इनपुट ["क्षेत्र", "लीड", "दीवार", "महिला", "गेंद"] जैसा है, तो आउटपुट [[ "दीवार", "क्षेत्र" होगा , "लीड", "लेडी"], ["बॉल", "एरिया", "लीड", "लेडी"]]

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

• एक नोड संरचना को परिभाषित करें, एक चर isEnd और चाइल्ड नोड्स की एक सूची होगी

• एक 2डी सरणी रेट परिभाषित करें

• एक फ़ंक्शन इन्सर्टनोड () को परिभाषित करें, यह सिर लेगा, s,

• नोड:=सिर

• इनिशियलाइज़ i:=0 के लिए, जब i <साइज़ ऑफ़ s, अपडेट (i से 1 तक बढ़ाएँ), करें -

  • एक्स:=एस [i]

  • यदि नोड का चाइल्ड ऐरे खाली है, तो -

    • नोड का बच्चा [x] :=नया नोड

  • नोड:=नोड का बच्चा[x]

• नोड का अंत:=सत्य

• getAllWords नामक फ़ंक्शन को परिभाषित करें, यह idx, उपसर्ग नोड और अस्थायी सरणी लेगा

• यदि नोड खाली है, तो -

  • वापसी

• यदि नोड का अंत सत्य है, तो -

  • अस्थायी के अंत में curr डालें

  • वापसी

• अगर idx>=उपसर्ग का आकार, तो −

  • प्रत्येक नोड के लिए यह नोड के बच्चे में -

    • getAllWords(idx, prefix, it.second, temp, curr + it.first)

• अन्यथा -

  • x :=उपसर्ग[idx]

  • यदि नोड का बच्चा खाली नहीं है, तो -

    • वापसी

  • getAllWords (idx + 1, उपसर्ग, बच्चे [x] नोड, अस्थायी, curr + x)

• फ़ंक्शन को हल करें () को परिभाषित करें, यह एक सरणी अस्थायी, idx, reqSize, सिर,

  लेगा

• यदि idx, reqSize के समान है, तो -

  • रिट के अंत में अस्थायी डालें

  • वापसी

• उपसर्ग:=खाली स्ट्रिंग

• प्रारंभ करने के लिए मैं:=0, जब मैं <अस्थायी का आकार, अद्यतन (मैं 1 से बढ़ाएँ), करते हैं -

  • उपसर्ग:=उपसर्ग + अस्थायी[i, idx]

• संभव सरणी परिभाषित करें

• वक्र =सिर

• getAllWords(0, उपसर्ग, वक्र, संभव)

• इनिशियलाइज़ करने के लिए:=0, जब i <साइज़ ऑफ़ संभव हो, अपडेट करें (i को 1 से बढ़ाएँ), करें -

  • एस:=संभव [i]

  • अस्थायी के अंत में s डालें

  • हल करें (अस्थायी, idx + 1, reqSize, सिर)

  • अस्थायी से अंतिम तत्व हटाएं

• मुख्य विधि से निम्न कार्य करें -

• सिर =नया नोड

• इनिशियलाइज़ i :=0 के लिए, जब i <शब्दों का आकार, अपडेट (i 1 से बढ़ाएँ), करें -

  • insertNode(सिर, शब्द[i])

• एक सरणी अस्थायी परिभाषित करें

• इनिशियलाइज़ i :=0 के लिए, जब i <शब्दों का आकार, अपडेट (i 1 से बढ़ाएँ), करें -

  • एस:=शब्द [i]

  • अस्थायी के अंत में s डालें

  • हल करें (अस्थायी, 1, शब्दों का आकार [0], सिर)

  • अस्थायी से अंतिम तत्व हटाएं

• वापसी रिट

उदाहरण

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
struct Node {
   bool isEnd;
   map<char, Node *> child;
};
class Solution {
public:
   vector<vector<string>> ret;
   void insertNode(Node *head, string &s) {
      Node *node = head;
      for (int i = 0; i < s.size(); i++) {
         char x = s[i];
         if (!node->child[x]) {
            node->child[x] = new Node();
         }
         node = node->child[x];
      }
      node->isEnd = true;
   }
   void getAllWords(int idx, string prefix, Node *node, vector<string>&temp,
      string curr = "") {
         if (!node)
            return;
         if (node->isEnd) {
            temp.push_back(curr);
            return;
         }
         if (idx >= prefix.size()) {
            for (auto &it : node->child) {
               getAllWords(idx, prefix, it.second, temp, curr + it.first);
            }
         }
         else {
            char x = prefix[idx];
            if (!node->child[x])
               return;
            getAllWords(idx + 1, prefix, node->child[x], temp, curr + x);
         }
   }
   void solve(vector<string> &temp, int idx, int reqSize, Node *head){
      if (idx == reqSize) {
         ret.push_back(temp);
         return;
      }
      string prefix = "";
      for (int i = 0; i < temp.size(); i++) {
         prefix += temp[i][idx];
      }
      vector<string> possible;
      Node *curr = head;
      getAllWords(0, prefix, curr, possible);
      for (int i = 0; i < possible.size(); i++) {
         string s = possible[i];
         temp.push_back(s);
         solve(temp, idx + 1, reqSize, head);
         temp.pop_back();
      }
   }
   vector<vector<string>> wordSquares(vector<string> &words) {
      ret.clear();
      Node *head = new Node();
      for (int i = 0; i < words.size(); i++) {
         insertNode(head, words[i]);
      }
      vector<string> temp;
      for (int i = 0; i < words.size(); i++) {
         string s = words[i];
         temp.push_back(s);
         solve(temp, 1, (int)words[0].size(), head);
         temp.pop_back();
      }
      return ret;
   }
};
main() {
   Solution ob;
   vector<string> v = {"area", "lead", "wall", "lady", "ball"};
   print_vector(ob.wordSquares(v));
}

इनपुट

{"area", "lead", "wall", "lady", "ball"}

आउटपुट

[[wall, area, lead, lady, ],[ball, area, lead, lady, ],]