Untitled

 avatar
unknown
plain_text
6 days ago
1.7 kB
2
Indexable
class TrieNode {
    boolean isCompleteWord;
    TrieNode[] children;

    public TrieNode() {
        this.isCompleteWord = false;
        this.children = new TrieNode[26]; // 26 for each alphabet character
    }
}
class WordDictionary {
    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

    // Insert a word into the Trie
    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int idx = ch - 'a'; // Convert character to index
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode(); // Create new child node
            }
            node = node.children[idx];
        }
        node.isCompleteWord = true; // Mark the end of the word
    }

    // Search for a word in the Trie
    public boolean search(String word) {
        return searchHelper(word, root);
    }

    private boolean searchHelper(String word, TrieNode node) {
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (ch == '.') { // Wildcard case
                for (TrieNode child : node.children) {
                    if (child != null && searchHelper(word.substring(i + 1), child)) {
                        return true;
                    }
                }
                return false; // If no child matches
            }
            int idx = ch - 'a';
            if (node.children[idx] == null) {
                return false; // If the character is not present
            }
            node = node.children[idx];
        }
        return node.isCompleteWord; // Check if it's a complete word
    }
}
Leave a Comment