[LintCode] 473 Add and Search Word 解题报告

Description
Design a data structure that supports the following two operations: addWord(word) and 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.

Notice
You may assume that all words are consist of lowercase letters a-z.


Example
addWord("bad")
addWord("dad")
addWord("mad")
search("pad")  // return false
search("bad")  // return true
search(".ad")  // return true
search("b..")  // return true


思路
这题一看就应该想到用Trie来解决。
主要是implement trie要细心。
find里面如果碰到"."，就把root下所有的都找一遍。只要里面能return true，就说明能找到。


Code

class TrieNode {
    public int R = 26;
    public TrieNode[] next;
    public boolean isWordEnd;
    
    public TrieNode() {
        this.next = new TrieNode[R];
        for (int i = 0; i < R; i++) {
            this.next[i] = null;
        }
        this.isWordEnd = false;
    }
}

public class WordDictionary {
    
    private TrieNode root;
    
    public WordDictionary() {
        root = new TrieNode();
    }

    // Adds a word into the data structure.
    public void addWord(String word) {
        // Write your code here
        TrieNode curr = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (curr.next[c - 'a'] == null) {
                curr.next[c - 'a'] = new TrieNode();
            }
            curr = curr.next[c - 'a'];
        }
        curr.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) {
        // Write your code here
        return findWord(root, word, 0);
    }
    
    public boolean findWord(TrieNode root, String word, int pos) {
        if (pos == word.length()) {
            return root.isWordEnd;
        }
        
        char c = word.charAt(pos);
        if (c == '.') {
            for (int i = 0; i < root.R; i++) {
                if (root.next[i] != null && findWord(root.next[i], word, pos + 1)) {
                    return true;
                }
            }
        }
        else if (root.next[c - 'a'] != null) {
            return findWord(root.next[c - 'a'], word, pos + 1);
        }
        return false;
    }
}

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