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)
Addsword
to the data structure, it can be matched later. -
bool search(word)
Returnstrue
if there is any string in the data structure that matchesword
orfalse
otherwise.word
may 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
-
word
inaddWord
consists lower-case English letters. -
word
insearch
consist of'.'
or lower-case English letters. - At most
50000
calls will be made toaddWord
andsearch
.
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.