My Java solution modified from Trie Tree using QUEUE


  • 1
    H
    class TrieNode {
        // Initialize your data structure here.
        TrieNode[] children;
        boolean end;
        public TrieNode() {
            children = new TrieNode[26];
            end = false;
        }
    }
    public class WordDictionary {
        private TrieNode root;
        WordDictionary() {
            root = new TrieNode();
        }
    
        // Adds a word into the data structure.
        public void addWord(String word) {
            TrieNode node = root;
            for(char c: word.toCharArray()) {
                if(node.children[c -'a'] == null) {
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c-'a'];
            }
            node.end = true;
        }
    
        // Returns if the word is in the data structure. A word could
        // contain the dot character '.' to represent any one letter.
        public boolean search(String word) {
            Queue<TrieNode> queue = new LinkedList<TrieNode>();
            queue.offer(root);
            for(char c: word.toCharArray()) {
                int size = queue.size();
                if (c == '.') {
                    for(int i = 0; i < size; i++) {
                        TrieNode node = queue.poll();
                        for(int j = 0; j <  26; j++){
                            if(node.children[j] != null) {
                                // System.out.println(j);
                                queue.offer(node.children[j]);
                            }
                        }
                    }
                } else {
                    for(int i = 0; i < size; i++) {
                        TrieNode node = queue.poll();
                        if(node.children[c -'a'] != null) {
                            queue.offer(node.children[c-'a']);
                        }
                    }
                }        
            }
            while (!queue.isEmpty()) {
                // System.out.println(queue.peek().end);
                if (queue.poll().end == true) return true;
            }
            return false;        
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.