Vuông từ (Word Squares) trong C++

Cho tập từ (duy nhất), tìm tất cả các "vuông từ" có thể xây dựng. Một dãy từ tạo thành vuông từ hợp lệ nếu hàng thứ k và cột thứ k đọc được cùng một chuỗi (0 ≤ k < max(số hàng, số cột)).

Ví dụ: ["ball", "area", "lead", "lady"] tạo vuông từ:

Input: ["area","lead","wall","lady","ball"] → Output: [["wall","area","lead","lady"], ["ball","area","lead","lady"]]

Phương pháp giải

Sử dụng Trie (cây tiền tố) để tìm từ có tiền tố cho trước. Backtracking: xây dựng vuông từ hàng bởi hàng. Tại hàng idx, tiền tố cần tìm là chuỗi ký tự thứ idx của các hàng đã chọn. Dùng Trie để lấy tất cả từ có tiền tố đó, thử từng từ và đệ quy.

Ví dụ chương trình

#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 (char c : s) {
            if (!node->child[c]) node->child[c] = new Node();
            node = node->child[c];
        }
        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;
        getAllWords(0, prefix, head, possible);
        for (string& s : possible) {
            temp.push_back(s);
            solve(temp, idx + 1, reqSize, head);
            temp.pop_back();
        }
    }
    
    vector> wordSquares(vector& words) {
        ret.clear();
        Node* head = new Node();
        for (string& w : words) insertNode(head, w);
        vector temp;
        for (string& s : words) {
            temp.push_back(s);
            solve(temp, 1, 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));
    return 0;
}

Đầu vào

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

Đầu ra

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