https://leetcode.com/problems/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.
解题思路：
这题实际上是 Implement Trie (Prefix Tree) 的follow-up。有了上一题的设计，这题唯一需要解决的，就是search这个方法，当遇到'.'的时候，如何办。
本题的addword()方法中，是没有'.'的，所以Trie树内肯定没有'.'。那么当遇到'.'的时候，只要递归search下一层次的所有子节点，有一个路径里找到，就返回true，否则立刻返回false。
public class WordDictionary {
class TrieNode {
// Initialize your data structure here.
boolean isWord;
Map<Character, TrieNode> next;
public TrieNode() {
next = new HashMap<Character, TrieNode>();
isWord = false;
}
}
private TrieNode root;
public WordDictionary() {
root = new TrieNode();
}
// Adds a word into the data structure.
public void addWord(String word) {
TrieNode cur = root;
for(int i = 0; i < word.length(); i++) {
if(cur.next.get(word.charAt(i)) == null) {
TrieNode next = new TrieNode();
cur.next.put(word.charAt(i), next);
}
cur = cur.next.get(word.charAt(i));
}
cur.isWord = 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 searchHelper(root, word);
}
public boolean searchHelper(TrieNode cur, String word) {
if(cur == null) {
return false;
}
for(int i = 0; i < word.length(); i++) {
if(word.charAt(i) != '.') {
cur = cur.next.get(word.charAt(i));
} else {
for(TrieNode value : cur.next.values()) {
if(searchHelper(value, word.substring(i + 1))) {
return true;
}
}
return false;
}
if(cur == null) {
return false;
}
}
return cur.isWord;
}
}
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");2018/6/20 二刷
class TrieNode {
HashMap<Character, TrieNode> node;
boolean isWord;
public TrieNode() {
node = new HashMap<Character, TrieNode>();
isWord = false;
}
}
public class WordDictionary {
/** Initialize your data structure here. */
public WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
if (!cur.node.containsKey(word.charAt(i))) {
TrieNode node = new TrieNode();
cur.node.put(word.charAt(i), node);
}
cur = cur.node.get(word.charAt(i));
}
cur.isWord = 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 searchHelper(root, word);
}
public boolean searchHelper(TrieNode cur, String word) {
for (int i = 0; i < word.length(); i++) {
if (word.charAt(i) == '.') {
// 这里是所有都没找到才返回false，不能直接return searchHelper(cur.node.get(key), word.substring(i + 1))
for (Character key : cur.node.keySet()) {
if (searchHelper(cur.node.get(key), word.substring(i + 1))) {
return true;
}
}
return false;
}
if (!cur.node.containsKey(word.charAt(i))) {
return false;
}
cur = cur.node.get(word.charAt(i));
}
return cur.isWord;
}
private TrieNode root;
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/