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 <= 500-
wordinaddWordconsists 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.