Use Trie and DFS ( Java Solution )


  • 0
    S
    public class WordDictionary {
        
        LetterNode head = new LetterNode('*');
    
        // Adds a word into the data structure.
        public void addWord(String word) {
            LetterNode cur = head;
            for(int i = 0;i < word.length();i++){
                if(cur.next.containsKey(word.charAt(i))){
                    cur = cur.next.get(word.charAt(i));
                }else{
                    LetterNode son = new LetterNode(word.charAt(i));
                    cur.next.put(word.charAt(i), son);
                    cur = son;
                }
            }
            cur.isEnd = 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) {
            // DFS
            return search(head, word, 0);
        }
        
        private boolean search(LetterNode node, String word, int layer){
            LetterNode son = null, dot = null;
            // ending case
            if(node == null) return false;
            if(layer == word.length()) return node.isEnd;
            
            // general case
            if(word.charAt(layer)=='.'){ 
                // Go though all next nodes when '.' appear
                Iterator iter = node.next.entrySet().iterator();
                while(iter.hasNext()){
                    Map.Entry pair = (Map.Entry)iter.next();
                    if(search((LetterNode)pair.getValue(), word, layer+1))
                        return true;
                }
            }else{
                // Go though target character node and '.' node
                if(node.next.containsKey(word.charAt(layer)))
                    son = node.next.get(word.charAt(layer));
                if(node.next.containsKey('.'))
                    dot = node.next.get('.');
                if(son!=null || dot!=null)
                    return search(son, word, layer+1) || search(dot, word, layer+1);
            }
                
            return false;
        }
        
        class LetterNode{
            Map<Character, LetterNode> next;
            char letter;
            boolean isEnd;
            LetterNode(char c){
                this.letter = c;
                this.next = new HashMap<Character, LetterNode>();
                this.isEnd = false;
            }
        }
    }
    
    // Your WordDictionary object will be instantiated and called as such:
    // WordDictionary wordDictionary = new WordDictionary();
    // wordDictionary.addWord("word");
    // wordDictionary.search("pattern");

  • 2
    G

    You actually don't need the layer parameter, see my solution:

    public class WordDictionary {
        Node root;
        public WordDictionary(){
            root = new Node();
        }
    
        // Adds a word into the data structure.
        public void addWord(String word) {
            if(search(word)){
                return;
            }
            
            Node current = root;
            for(int i=0; i < word.length(); i++){
                char c = word.charAt(i);
                if(current.children[c - 'a'] != null){
                    current = current.children[c - 'a'];
                }else{
                    current.children[c - 'a'] = new Node(c);
                    current = current.children[c - 'a'];
                }
            }
            current.isEnd = 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) {
            return search(root, word);
        }
        
        public boolean search(Node root, String word){
            if(word == null || word.length() == 0){
                return root.isEnd;
            }
            
            Node current = root;
            for(int i=0; i < word.length(); i++){
                char c = word.charAt(i);
                // check every possibility for '.'
                if(c == '.'){
                    for(Node child: current.children){
                        if(child != null){
                           if(search(child, word.substring(i+1, word.length()))){
                               return true;
                           }
                        }
                    }
                    return false;
                }
                
                if(current.children[c - 'a'] != null){
                    current = current.children[c - 'a'];
                }else{
                    return false;
                }
            }
            
            if(current.isEnd){
                return true;
            }else{
                return false;
            }
        }
    }
    
    class Node {
        Node[] children;
        char c;
        boolean isEnd = false;
        public Node(){
            children = new Node[26];
        }
        
        public Node(char c){
            this.c = c;
            children = new Node[26];
        }
    }
    
    // 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.