leetcode 211 Trie的添加及搜索
Design a data structure that supports adding new words and finding if a string matches any previously added string.
Implement the WordDictionary class:
WordDictionary()Initializes the object.void addWord(word)Addswordto the data structure, it can be matched later.bool search(word)Returnstrueif there is any string in the data structure that matcheswordorfalseotherwise.wordmay contain dots'.'where dots can be matched with any letter.
Example:
Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
Constraints:
1 <= word.length <= 500wordinaddWordconsists lower-case English letters.wordinsearchconsist of'.'or lower-case English letters.- At most
50000calls will be made toaddWordandsearch.
Hide Hint #1
使用HashMap
开始想法是使用Set方式但是在单词初始时，由于同时需要比较单词长度和内容，出现limit time， 后来在讨论区找到以下方案， 将单词的长度做为key， 长度相同再比较内容：
java
class WordDictionary {
// 定义一个hashset，存放root
//private Set< String> dict;
private final Map< Integer, Set<String>> dict;
/** Initialize your data structure here. */
public WordDictionary() {
dict = new HashMap<>();
}
public void addWord(String word) {
int n = word.length();
//dict.add(word);
dict.computeIfAbsent(n, f->new HashSet<>()).add(word);
return ;
}
public boolean search(String word) {
int n = word.length();
if( dict.containsKey(n) == false) {
return false;
}
for (String s: dict.get(n)) {
int i=0;
while (i<n && (s.charAt(i) == word.charAt(i) || word.charAt(i)=='.') )
i++;
if (i==n ){
return true;
}
}
return false;
}
}
使用Trie树
class TrieNode {
char c;
HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
boolean isLeaf;
public TrieNode() {}
public TrieNode(char c){
this.c = c;
}
}
class WordDictionary {
private TrieNode root;
public WordDictionary() {
root = new TrieNode();
}
public void addWord(String word) {
HashMap<Character, TrieNode> children = root.children;
for(int i =0; i<word.length();i++){
char c = word.charAt(i);
TrieNode t = null;
if (children.containsKey(c)){
t = children.get(c);
} else {
t = new TrieNode(c);
children.put(c,t);
}
children = t.children;
if (i == word.length()-1){
t.isLeaf = true;
}
}
}
public boolean search(String word) {
return dfsSearch(root.children, word, 0);
}
public boolean dfsSearch(HashMap<Character, TrieNode>children, String word, int start) {
if (start == word.length()){
if (children.size() == 0){
return true;
}
else {
return false;
}
}
char c = word.charAt(start);
// 字母
if( children.containsKey(c) ) {
// 查询单词长度相等且非前缀
if (start == word.length()-1 && children.get(c).isLeaf) {
return true;
}
// 继续查找
return dfsSearch(children.get(c).children, word, start+1);
//通配符
} else if (c == '.'){
boolean result = false;
for (Map.Entry<Character, TrieNode >child: children.entrySet()){
if (start == word.length()-1 && child.getValue().isLeaf){
return true;
}
if (dfsSearch(child.getValue().children, word, start+1)){
result = true;
}
}
return result;
}else {
return false;
}
}
}
Python语言一些实现
1）使用字典方式构造
class WordDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root ={}
def addWord(self, word: str) -> None:
node = self.root
for char in word:
node = node.setdefault(char, {})
node[None] = None
def search(self, word: str) -> bool:
def find(word, node):
if not word:
return None in node
char, word = word[0], word[1:]
if char != '.':
return char in node and find(word,node[char])
return any(find(word,kid) for kid in node.values() if kid)
return find(word, self.root)
这个版本python实现，使用了字典做为子节点类似下面这种结构：
root = {'b':{'i':{'g':{None, None}}, 'a':{'d':{None, None}}}, 'c':{None:None}}
find的实现可以表示为
def find(word, node):
if not word:
return None in node
char, word = word[0], word[1:]
if char != '.':
return char in node and find(word, node[char])
li = []
for kid in node.values():
if kid:
li.append( find(word, kid))
if not li:
return None in node
re = False
for kid in li:
re = re or kid
return re
找到None认为找到单词， 遇到通配符’.’ ， 以前是一个分支的递归查找， 改为多个分支递归查找 ， kid in node.values(), 只要有一个满足要求即可反馈成功， 也就是any的作用
2）在看一下StefanPochmann 写的另外一个实现
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word):
node = self.root
for char in word:
node = node.setdefault(char, {})
node['$'] = None
def search(self, word):
nodes = [self.root]
for char in word + '$':
nodes = [kid for node in nodes for kid in
([node[char]] if char in node else
filter(None, node.values()) if char == '.' else [])]
return bool(nodes)
具体思路和上面一样子只是写得更简洁一些， one-lines, 感觉这种不太适合我这样的初学者， 看得有点头疼
直到这个贴子才有些理解。 这篇文章作者还专门出了一本 Python One-Liners 的书。
针对search拆解如下
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word):
node = self.root
for char in word:
node = node.setdefault(char, {})
node['$'] = None
def search(self, word):
nodes = [self.root]
for char in word + '$':
# node 是字典结构 dict
kid=[]
for node in nodes:
li=[]
if char in node:
li = [node[char]]
else:
# 当前节点下所有的值
if char == '.':
li = filter(None, node.values())
else:
li = []
kid.extend(li)
nodes=[]
nodes.extend(kid)
# nodes = copy.deepcopy(kid)
#print(nodes)
return bool(nodes)
这里的结束符号由None改了’$’, 使用None通过char 是无法遍历的。
参考及引用：
LeetCode – Add and Search Word – Data structure design (Java)
Photo by Jη ✿@Jeanne_8L from twitter
Comments are closed.