Monday, August 31, 2015

Leetcode: Add and Search Word - Data structure design

Design a data structure that supports the following two operations:
void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.
You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

Understand the problem:
Use Trie + DFS

Code (Java):
public class WordDictionary {
    class TrieNode {
        char val;
        boolean leaf;
        TrieNode[] children;
        
        public TrieNode() {
            this.val = '\0';
            this.leaf = false;
            this.children = new TrieNode[26];
        }
        
        public TrieNode(char val, boolean leaf) {
            this.val = val;
            this.leaf = leaf;
            this.children = new TrieNode[26];
        }
    }
    
    private TrieNode root = new TrieNode();
    private TrieNode dummyRoot = root;
    
    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode curr = root;
        int offset = 'a';
        int i = 0;
        for (i = 0; i < word.length(); i++) {
            char character = word.charAt(i);
            if (curr.children[character - offset] == null) {
                curr.children[character - offset] = 
                    new TrieNode(character, i == word.length() - 1 ? true : false);
            } else {
                if (i == word.length() - 1) {
                    curr.children[character - offset].leaf = true;
                }
            }
            
            curr = curr.children[character - offset];
        }
    }

    // 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;
        }
        
        TrieNode curr = root;
        int offset = 'a';
        for (int i = 0; i < word.length(); i++) {
            char character = word.charAt(i);
            if (character != '.') {
                if (curr.children[character - offset] == null) {
                    return false;
                }
                curr = curr.children[character - offset];
            } else {
                // DFS
                for (int j = 0; j < 26; j++) {
                    if (curr.children[j] != null) {
                        if (i == word.length() - 1 && curr.children[j].leaf) {
                            root = dummyRoot;
                            return true;
                        }
                        
                        root = curr.children[j];
                        if (search(word.substring(i + 1))) {
                            root = dummyRoot;
                            return true;
                        }
                    }
                }
                root = dummyRoot;
                return false;
            }
        }
        
        if (curr != null && curr.leaf == false) {
            return false;
        }
        
        return true;
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");


Update on 10/19/15:
Updated neat version without saving the value for a TrieNode. 
There are mainly two tricks in the problem:
  -- The first trick is, in the DFS, we need to change the root of the Trie, and don't forget to change it back. 
  -- The second trick is, when we tried all 26 possibilities without getting an answer, we must return false instead. 

public class WordDictionary {
    private Trie trie = new Trie();
    
    // Adds a word into the data structure.
    public void addWord(String word) {
        trie.add(word);
    }

    // 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 trie.search(word);
    }
    
    class Trie {
        private TrieNode root = new TrieNode();
        private TrieNode rootCopy = root;
        
        // Add a word
        void add(String word) {
            TrieNode p = root;
            
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (p.children[c- 'a'] != null) {
                    p = p.children[c - 'a'];
                } else {
                    p.children[c - 'a'] = new TrieNode();
                    p = p.children[c - 'a'];
                }
                
                if (i == word.length() - 1) {
                    p.leaf = true;
                }
            }
        }
        
        boolean search(String word) {
            TrieNode p = root;
            
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                
                if (c == '.') {
                    for (int j = 0; j < 26; j++) {
                        if (p.children[j] != null) {
                            // Change the root pointer
                            root = p.children[j];
                            
                            if (search(word.substring(i + 1))) {
                                root = rootCopy;
                                return true;
                            }
                            
                            // Change back the root pointer
                            root = rootCopy;
                        }
                    }
                    // If none of them get true, return false;                   
                    return false;
                } else {
                    if (p.children[c - 'a'] == null) {
                        return false;
                    }
                    p = p.children[c - 'a'];
                }
            }
            
            if (!p.leaf) {
                return false;
            }
            
            return true;
        }
    }
    
    class TrieNode {
        TrieNode[] children;
        boolean leaf;
        
        public TrieNode() {
            children = new TrieNode[26];
        }
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

No comments:

Post a Comment