C++ এ ওয়ার্ড স্কোয়ার

উদাহরণ

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

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