Untitled
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