वर्ड स्क्वेयर्स - C++

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

तो, यदि इनपुट ["area","lead","wall","lady","ball"] जैसा है, तो आउटपुट [["wall", "area", "lead", "lady"], ["ball", "area", "lead", "lady"]] होगा

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

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

• एक 2D ऐरे ret परिभाषित करें

• insertNode() नामक एक फ़ंक्शन परिभाषित करें, जो head, s लेगा,

• node := head

• i := 0 से आरंभ करें, जब i, s के आकार से कम, अद्यतन करें (i को 1 से बढ़ाएं), करें −

  • x := s[i]

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

    • node का child[x] := नया नोड

  • node := node का child[x]

• node का isEnd := true

• getAllWords नामक एक फ़ंक्शन परिभाषित करें, जो idx, prefix, node और temp ऐरे लेगा

• यदि node खाली है, तो −

  • लौटें

• यदि node का isEnd true है, तो −

  • curr को temp के अंत में डालें

  • लौटें

• यदि idx >= prefix का आकार, तो −

  • node के चाइल्ड में प्रत्येक नोड it के लिए −

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

• अन्यथा −

  • x := prefix[idx]

  • यदि node का चाइल्ड खाली नहीं है, तो −

    • लौटें

  • getAllWords(idx + 1, prefix, node का child[x], temp, curr + x)

• solve() नामक एक फ़ंक्शन परिभाषित करें, जो एक ऐरे temp, idx, reqSize, head लेगा,

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

  • temp को ret के अंत में डालें

  • लौटें

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

• i := 0 से आरंभ करें, जब i, temp के आकार से कम, अद्यतन करें (i को 1 से बढ़ाएं), करें −

  • prefix := prefix + temp[i, idx]

• possible नामक एक ऐरे परिभाषित करें

• curr = head

• getAllWords(0, prefix, curr, possible)

• i := 0 से आरंभ करें, जब i, possible के आकार से कम, अद्यतन करें (i को 1 से बढ़ाएं), करें −

  • s := possible[i]

  • s को temp के अंत में डालें

  • solve(temp, idx + 1, reqSize, head)

  • temp से अंतिम तत्व हटाएं

• मुख्य विधि से निम्नलिखित करें −

• head = नया नोड

• i := 0 से आरंभ करें, जब i, words के आकार से कम, अद्यतन करें (i को 1 से बढ़ाएं), करें −

  • insertNode(head, words[i])

• एक ऐरे temp परिभाषित करें

• i := 0 से आरंभ करें, जब i, words के आकार से कम, अद्यतन करें (i को 1 से बढ़ाएं), करें −

  • s := words[i]

  • s को temp के अंत में डालें

  • solve(temp, 1, words[0] का आकार, head)

  • temp से अंतिम तत्व हटाएं

• ret लौटाएं

उदाहरण 

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

#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, ],]