In các từ hợp lệ từ mảng ký tự trong C++

Cho một tập từ điển và một mảng ký tự. Tìm tất cả các từ trong từ điển có thể tạo ra chỉ sử dụng các ký tự từ mảng (mỗi ký tự dùng tối đa một lần). Ví dụ: từ điển {go, hi, run, on, hog, gone}, mảng {a, o, h, g}. Kết quả: go, hog.

Cây Trie

Sử dụng cấu trúc Trie để lưu từ điển. Duyệt Trie, chỉ đi vào nhánh có ký tự tồn tại trong mảng cho trước. Khi gặp nút lá, in từ tìm được.

Ví dụ minh họa

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

struct TrieNode {
    TrieNode* child[26];
    bool isLeaf;
    TrieNode() {
        isLeaf = false;
        fill(begin(child), end(child), nullptr);
    }
};

void insert(TrieNode* root, const string& word) {
    TrieNode* cur = root;
    for (char c : word) {
        int idx = c - 'a';
        if (!cur->child[idx]) cur->child[idx] = new TrieNode();
        cur = cur->child[idx];
    }
    cur->isLeaf = true;
}

void findWords(TrieNode* node, bool allowed[], string current) {
    if (node->isLeaf) cout << current << '\t';
    for (int i = 0; i < 26; i++)
        if (allowed[i] && node->child[i])
            findWords(node->child[i], allowed, current + char('a'+i));
}

void printValidWords(char arr[], TrieNode* root, int n) {
    bool allowed[26] = {false};
    for (int i = 0; i < n; i++) allowed[arr[i]-'a'] = true;
    
    string start = "";
    for (int i = 0; i < 26; i++)
        if (allowed[i] && root->child[i])
            findWords(root->child[i], allowed, string(1, 'a'+i));
}

int main() {
    string dict[] = {"go", "hi", "run", "on", "hog", "gone"};
    TrieNode* root = new TrieNode();
    for (auto& w : dict) insert(root, w);
    
    char arr[] = {'a', 'o', 'g', 'h'};
    cout << "Các từ hợp lệ: ";
    printValidWords(arr, root, 4);
    return 0;
}

Kết quả

Các từ hợp lệ: go    hog