#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <stdexcept>
using namespace std;

class WordFinder {
public:
    struct Node {
        char c;
        unordered_map<char, Node*> children;
        bool end = false;
        
        Node() : c(0), end(false) {}
        Node(char ch) : c(ch), end(false) {}
        
        // In a complete solution, you'd want to add a destructor to free children.
        ~Node() {
            for (auto &entry : children) {
                delete entry.second;
            }
        }
    };

    Node* root;
    vector<char> charC;

    // Constructor: builds the trie from a list of words and copies the search characters.
    WordFinder(vector<string>& words, vector<char>& c) {
        root = new Node();
        charC = c;
        for (const string &w : words) {
            insert(w);
        }
    }

    // Destructor to free allocated memory.
    ~WordFinder() {
        delete root;
    }
    
    /** Inserts a word into the trie. */
    void insert(const string &word) {
        Node* temp = root;
        for (char a : word) {
            // Use unordered_map to check for the child.
            if (temp->children.find(a) == temp->children.end()) {
                temp->children[a] = new Node(a);
            }
            temp = temp->children[a];
        }
        temp->end = true;
    }

    // Recursive helper function to find words given available characters.
    void find_r(vector<char>& chars, Node* cn, string curr_word, unordered_set<string>& res) {
        if (cn == nullptr) return;
        if (cn->end) {
            res.insert(curr_word);
        }
        for (size_t i = 0; i < chars.size(); i++) {
            if (chars[i] == '*') continue;
            char temp = chars[i];
            // Mark the character as used.
            chars[i] = '*';
            // Only proceed if there is a valid child.
            if (cn->children.find(temp) != cn->children.end()) {
                find_r(chars, cn->children[temp], curr_word + temp, res);
            }
            // Restore the character.
            chars[i] = temp;
        }
    }
    
    // Public function to initiate the word finding process.
    unordered_set<string> find() {
        unordered_set<string> res;
        find_r(charC, root, "", res);
        return res;
    }
};

int main() {
    vector<string> words = {"word", "words", "wood", "order"};
    vector<char> c = {'o','r','s','d','o','w','e'};
    WordFinder wf(words, c);
    unordered_set<string> res = wf.find();
    for (const auto& r : res) {
        cout << r << endl;
    }
    return 0;
}