class TrieNode {
    bool isEndOfWord;                    // Marks complete words
    unordered_map<char, TrieNode*> mp;  // Children nodes (26 letters max)
};

class Trie {
    TrieNode* root;
    // Insert, Search, Delete, AutoComplete, Suggestions
};

bool searchTrie(const string& word) {
    TrieNode* crawler = root;
    for (char c : word) {
        if (crawler->mp.find(c) == crawler->mp.end())
            return false;  // Character not found
        crawler = crawler->mp[c];
    }
    return crawler->isEndOfWord;  // Must be complete word
}

vector<string> autoComplete(const string& prefix) {
    // 1. Navigate to prefix node
    TrieNode* crawler = root;
    for (char c : prefix) {
        if (!crawler->mp.count(c)) return {};  // Prefix doesn't exist
        crawler = crawler->mp[c];
    }
    
    // 2. DFS to collect all words from this node
    vector<string> results;
    findWords(crawler, prefix, results);  // Recursive traversal
    return results;
}

vector<string> getSuggestions(const string& word) {
    unordered_set<string> candidates;
    
    // Generate all possible 1-edit variations
    for (int i = 0; i < word.length(); i++) {
        // Deletion: "helo" → "hlo", "elo", "heo", "hel"
        candidates.insert(word.substr(0, i) + word.substr(i+1));
        
        // Substitution: "helo" → "aelo", "belo", ..., "helz"
        for (char c = 'a'; c <= 'z'; c++) {
            string temp = word;
            temp[i] = c;
            candidates.insert(temp);
        }
        
        // Transposition: "helo" → "ehlo", "hleo", "heol"
        if (i < word.length() - 1) {
            string temp = word;
            swap(temp[i], temp[i+1]);
            candidates.insert(temp);
        }
    }
    
    // Insertion: "helo" → "ahelo", "haelo", ..., "heloz"
    for (int i = 0; i <= word.length(); i++) {
        for (char c = 'a'; c <= 'z'; c++) {
            candidates.insert(word.substr(0, i) + c + word.substr(i));
        }
    }
    
    // Filter: Keep only valid dictionary words
    vector<string> valid;
    for (const string& candidate : candidates) {
        if (searchTrie(candidate)) valid.push_back(candidate);
    }
    return valid;
}