211. 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

思路:用Trie来实现, Search的时候关键在于’.’的处理, 这里可以递归实现. 递归的时候每次都取第一个字符来c判断:
1.c为’.’: 需要递归搜索当前TrieNode的children是否包含word的下一个字符。
2.c不为’.’:
1,如果当前trieNode的children里不存在c,返回false.
2, 如果当前trieNode里存在c, 则trieNode更新下,word取下一个字符,然后递归

public class WordDictionary {
    public class TrieNode {
        HashMap<Character, TrieNode> children;
        boolean hasWord;
        public TrieNode() {
            children = new HashMap<>();
            hasWord = true;
        }
    }

    TrieNode root;

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

    // Adds a word into the data structure.
    public void addWord(String word) {
        if (word == null || word.length() == 0) return;
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!current.children.containsKey(c)) {
                current.children.put(c, new TrieNode());
            }
            current = current.children.get(c);
        }
        current.hasWord = 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(word, root);
    }

    public boolean search(String word, TrieNode current) {
        if (current == null || word.length() == 0 || word == null) return true;
        char c = word.charAt(0);
        if (c != '.') {
            if (!current.children.containsKey(c)) {
                return false;
            } else {
                current = current.children.get(c);
                return search(word.substring(1), current);
            }

        } else { // '.' search all children for 
            for(TrieNode child: current.children.values()) {
                if (search(word.substring(1), child)) {
                    return true;
                }
            }
        }
        return false;
    }
}

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s