Word Squares ใน C++

สมมติว่าเรามีชุดคำ (ทุกคำไม่ซ้ำกัน) เราต้องหา Word Squares ทั้งหมดที่สร้างได้จากชุดคำนั้น ลำดับของคำจะสร้าง Word Square ที่ถูกต้องได้ หากแถวที่ k และคอลัมน์ที่ k อ่านได้สตริงเดียวกัน โดยที่ 0 ≤ k < max(จำนวนแถว, จำนวนคอลัมน์) ตัวอย่างเช่น ลำดับคำ ["ball","area","lead","lady"] จะสร้าง Word Square ได้ เพราะแต่ละคำอ่านเหมือนกันทั้งแนวนอนและแนวตั้ง

เช่น ถ้าอินพุตคือ ["area","lead","wall","lady","ball"] ผลลัพธ์จะเป็น [["wall","area","lead","lady"], ["ball","area","lead","lady"]]

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:

• กำหนดโครงสร้างโหนด Trie มีตัวแปร isEnd และ map child
• สร้าง Trie จากคำทั้งหมด
• ใช้ Backtracking: เริ่มจากคำแรก แล้วสร้าง prefix จากคอลัมน์ปัจจุบัน ค้นหาคำที่ขึ้นต้นด้วย prefix ใน Trie ใส่ต่อ แล้วเรียกซ้ำจนครบจำนวนคำ
• เก็บผลลัพธ์ที่สมบูรณ์

ตัวอย่าง

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector> v){
    cout << "[";
    for(int i = 0; i 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;
    }
};
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"]]