C++-এ ওয়ার্ড স্কোয়ার (Word Squares) বের করা

ধরি আমাদের একটি শব্দের সেট আছে (সবই уникаল)। আমাদের এই শব্দ들 থেকে তৈরি হতে পারা সব ওয়ার্ড স্কোয়ার বের করতে হবে। একটি শব্দ সিকোয়েন্স ভ্যালিড ওয়ার্ড স্কোয়ার হবে যদি k-তম সারি এবং k-তম কলাম একই স্ট্রিং পড়া যায়, যেখানে 0 ≤ k < max(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 থেকে s.size()-1 পর্যন্ত:
    • x := s[i]
    • যদি node->child[x] না থাকে: node->child[x] = নতুন নোড
    • node := node->child[x]
  • node->isEnd = true
• getAllWords ফাংশন সংজ্ঞায়িত: এটি idx, prefix, node, temp অ্যারে নিবে।
  • যদি node নাল: ফেরত।
  • যদি node->isEnd: curr-কে temp-তে পুশ, ফেরত।
  • যদি idx >= prefix.size():
    • node->child-এর প্রতিটি it کے জন্য: getAllWords(idx, prefix, it.second, temp, curr + it.first)
  • অন্যথায়:
    • x := prefix[idx]
    • যদি node->child[x] না থাকে: ফেরত।
    • getAllWords(idx+1, prefix, node->child[x], temp, curr + x)
• solve() ফাংশন সংজ্ঞায়িত: এটি temp অ্যারে, idx, reqSize, head নিবে।
  • যদি idx == reqSize: temp-কে ret-তে পুশ, ফেরত।
  • prefix := খালি স্ট্রিং
  • i = 0 থেকে temp.size()-1 পর্যন্ত: prefix += temp[i][idx]
  • possible অ্যারে সংজ্ঞায়িত।
  • curr = head; getAllWords(0, prefix, curr, possible)
  • i = 0 থেকে possible.size()-1 পর্যন্ত:
    • s := possible[i]
    • s-কে temp-তে পুশ
    • solve(temp, idx+1, reqSize, head)
    • temp-র শেষ উপাদান পপ
• মেইন মেথড থেকে:
  • head = নতুন নোড
  • সব শব্দের জন্য insertNode(head, words[i])
  • temp অ্যারে সংজ্ঞায়িত।
  • প্রতিটি শব্দ s জন্য:
    • s-কে temp-তে পুশ
    • solve(temp, 1, words[0].size(), head)
    • temp-র শেষ উপাদান পপ
  • ret ফেরত।

প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector> 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 child;
};

class Solution {
public:
    vector> 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& 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 &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 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> wordSquares(vector &words) {
        ret.clear();
        Node *head = new Node();
        for (int i = 0; i < words.size(); i++) {
            insertNode(head, words[i]);
        }
        vector 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;
    }
};

int main() {
    Solution ob;
    vector v = {"area", "lead", "wall", "lady", "ball"};
    print_vector(ob.wordSquares(v));
}

ইনপুট

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

আউটপুট

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