trie.cpp

/*
Trie (Prefix Tree) Patterns
Mathematical Foundation: Tree structure for string retrieval
Space: O(ALPHABET_SIZE * N * M) where N=words, M=avg length
Time: Insert/Search O(M), Applications: Auto-complete, spell check
*/

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

// Basic Trie Implementation
// LeetCode: 208. Implement Trie (Prefix Tree)
// https://leetcode.com/problems/implement-trie-prefix-tree/
class Trie {
public:
    struct TrieNode {
        TrieNode* children[26];
        bool isEnd;
        TrieNode() {
            for (int i = 0; i < 26; i++) children[i] = nullptr;
            isEnd = false;
        }
    };
    
    TrieNode* root;
    
    Trie() { root = new TrieNode(); }
    
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) return false;
            node = node->children[idx];
        }
        return node->isEnd;
    }
    
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx]) return false;
            node = node->children[idx];
        }
        return true;
    }
};

// Add and Search Word - Data structure design
// LeetCode: 211. Design Add and Search Words Data Structure
// https://leetcode.com/problems/design-add-and-search-words-data-structure/
class WordDictionary {
    struct TrieNode {
        TrieNode* children[26] = {};
        bool isEnd = false;
    };
    
    TrieNode* root;
    
public:
    WordDictionary() { root = new TrieNode(); }
    
    void addWord(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        function<bool(TrieNode*, int)> dfs = [&](TrieNode* node, int i) -> bool {
            if (i == word.size()) return node->isEnd;
            if (word[i] == '.') {
                for (auto child : node->children) {
                    if (child && dfs(child, i + 1)) return true;
                }
                return false;
            } else {
                int idx = word[i] - 'a';
                return node->children[idx] && dfs(node->children[idx], i + 1);
            }
        };
        return dfs(root, 0);
    }
};

// Word Search II (Using Trie)
// LeetCode: 212. Word Search II
// https://leetcode.com/problems/word-search-ii/
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    struct TrieNode {
        TrieNode* children[26] = {};
        string* word = nullptr;
    };
    
    TrieNode* root = new TrieNode();
    
    // Build trie
    for (string& w : words) {
        TrieNode* node = root;
        for (char c : w) {
            int idx = c - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->word = &w;
    }
    
    vector<string> res;
    int m = board.size(), n = board[0].size();
    
    function<void(int, int, TrieNode*)> dfs = [&](int r, int c, TrieNode* node) {
        if (r < 0 || r >= m || c < 0 || c >= n) return;
        
        char ch = board[r][c];
        if (ch == '#' || !node->children[ch - 'a']) return;
        
        node = node->children[ch - 'a'];
        if (node->word) {
            res.push_back(*node->word);
            node->word = nullptr; // Avoid duplicates
        }
        
        board[r][c] = '#';
        dfs(r+1, c, node); dfs(r-1, c, node); dfs(r, c+1, node); dfs(r, c-1, node);
        board[r][c] = ch;
    };
    
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            dfs(r, c, root);
        }
    }
    return res;
}

// Replace Words
// LeetCode: 648. Replace Words
// https://leetcode.com/problems/replace-words/
string replaceWords(vector<string>& dictionary, string sentence) {
    struct TrieNode {
        TrieNode* children[26] = {};
        bool isEnd = false;
    };
    
    TrieNode* root = new TrieNode();
    
    // Build trie
    for (string& word : dictionary) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->isEnd = true;
    }
    
    auto findRoot = [&](string& word) -> string {
        TrieNode* node = root;
        string root_word;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) break;
            node = node->children[idx];
            root_word += c;
            if (node->isEnd) return root_word;
        }
        return word;
    };
    
    stringstream ss(sentence);
    string word, result;
    bool first = true;
    while (ss >> word) {
        if (!first) result += " ";
        result += findRoot(word);
        first = false;
    }
    return result;
}

// Longest Word in Dictionary
// LeetCode: 720. Longest Word in Dictionary
// https://leetcode.com/problems/longest-word-in-dictionary/
string longestWord(vector<string>& words) {
    struct TrieNode {
        TrieNode* children[26] = {};
        bool isEnd = false;
    };
    
    TrieNode* root = new TrieNode();
    
    for (string& word : words) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->isEnd = true;
    }
    
    string result;
    
    function<void(TrieNode*, string)> dfs = [&](TrieNode* node, string path) {
        if (path.size() > result.size() || 
            (path.size() == result.size() && path < result)) {
            result = path;
        }
        
        for (int i = 0; i < 26; i++) {
            if (node->children[i] && node->children[i]->isEnd) {
                dfs(node->children[i], path + char('a' + i));
            }
        }
    };
    
    dfs(root, "");
    return result;
}

// Concatenated Words
// LeetCode: 472. Concatenated Words
// https://leetcode.com/problems/concatenated-words/
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
    struct TrieNode {
        TrieNode* children[26] = {};
        bool isEnd = false;
    };
    
    TrieNode* root = new TrieNode();
    
    for (string& word : words) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->isEnd = true;
    }
    
    auto canForm = [&](string& word) -> bool {
        int n = word.size();
        vector<bool> dp(n + 1);
        dp[0] = true;
        
        for (int i = 1; i <= n; i++) {
            TrieNode* node = root;
            for (int j = i - 1; j >= 0; j--) {
                int idx = word[j] - 'a';
                if (!node->children[idx]) break;
                node = node->children[idx];
                if (node->isEnd && dp[j] && (j > 0 || i < n)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    };
    
    vector<string> result;
    for (string& word : words) {
        if (canForm(word)) result.push_back(word);
    }
    return result;
}

// Short Encoding of Words
// LeetCode: 820. Short Encoding of Words
// https://leetcode.com/problems/short-encoding-of-words/
int minimumLengthEncoding(vector<string>& words) {
    struct TrieNode {
        TrieNode* children[26] = {};
        int depth = 0;
    };
    
    TrieNode* root = new TrieNode();
    vector<TrieNode*> leaves;
    
    for (const string& word : unordered_set<string>(words.begin(), words.end())) {
        TrieNode* node = root;
        for (int i = word.size() - 1; i >= 0; i--) {
            int idx = word[i] - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
            node->depth = root->depth - i + word.size();
        }
        leaves.push_back(node);
    }
    
    int ans = 0;
    for (TrieNode* leaf : leaves) {
        bool isLeaf = true;
        for (auto child : leaf->children) {
            if (child) { isLeaf = false; break; }
        }
        if (isLeaf) ans += leaf->depth + 1;
    }
    return ans;
}

// Auto-complete suggestions (Common interview question)
vector<string> autoComplete(Trie& trie, string prefix) {
    vector<string> suggestions;
    
    function<void(Trie::TrieNode*, string)> dfs = [&](Trie::TrieNode* node, string current) {
        if (node->isEnd) suggestions.push_back(current);
        if (suggestions.size() >= 3) return; // Limit suggestions
        
        for (int i = 0; i < 26; i++) {
            if (node->children[i]) {
                dfs(node->children[i], current + char('a' + i));
            }
        }
    };
    
    // Navigate to prefix
    Trie::TrieNode* node = trie.root;
    for (char c : prefix) {
        int idx = c - 'a';
        if (!node->children[idx]) return suggestions;
        node = node->children[idx];
    }
    
    dfs(node, prefix);
    return suggestions;
}