Java Solution


  • 0
    P
        private Node root;
        public WordDictionary() {
            this.root = new Node();
        }
        // Adds a word into the data structure.
        public void addWord(String word) {
            if (word == null || word.length() == 0) return;
            Node node = root;
            for(Character c : word.toCharArray()) {
                if (node.nodes[c - 'a'] == null) {
                    node.nodes[c - 'a'] = new Node(c);
                }
                node = node.nodes[c - 'a'];
            }
            node.isWordEnd = 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) {
            if (word == null || word.length() == 0) return false;
            Node node = root;
            return search(word, 0, root);
        }
        
        private boolean search(String word, int position, Node node) {
            char c = word.charAt(position);
            if (c == '.') {
                for(Node childNode : node.nodes) {
                    if (childNode != null) {
                        if (word.length() - 1 == position){
                            if (childNode.isWordEnd) return true;
                        } else { 
                            if (search(word, position + 1, childNode)) return true;
                        }
                    }
                }
            } else {
                if (node.nodes[c - 'a'] != null) {
                    if (word.length() - 1 == position) return node.nodes[c - 'a'].isWordEnd;
                    return search(word, position + 1, node.nodes[c - 'a']);
                }
            }
            return false;
        }
        
        private class Node {
            Node[] nodes;
            char chr;
            boolean isWordEnd;
            public Node() {
                nodes = new Node[26];
            }
            public Node(char c) {
                this();
                chr = c;
            }
        }
    }
    
    // Your WordDictionary object will be instantiated and called as such:
    // WordDictionary wordDictionary = new WordDictionary();
    // wordDictionary.addWord("word");
    // wordDictionary.search("pattern");
    

Log in to reply
 

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