https://leetcode.com/problems/add-and-search-word-data-structure-design/
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/211_Add_and_Search_Word_Data_Structure_Design.java
follow up是虽然这个已经是optimal的⽅法,有没有可能让search更更快⼀一
点,表示在insert的时候就把“.”也当做⼀一个node加进去,⽐比如如果insert
“cat”, 那么第⼀一 层就是 “c”,".",第⼆二层是“a”,"." | "a","."
讨论:这道题有个很好的Follow up,就是当搜索的单词中存在星号怎么搞,星号的定义和Wildcard Matching中一样,可以代表任意的字符串,包括空字符串,请参见评论区1楼
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.
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
https://leetcode.com/problems/add-and-search-word-data-structure-design/discuss/59554/My-simple-and-clean-Java-codeYou may assume that all words are consist of lowercase letters
a-z
Using backtrack to check each character of word to search.
public class WordDictionary {
public class TrieNode {
public TrieNode[] children = new TrieNode[26];
public String item = "";
}
private TrieNode root = new TrieNode();
public void addWord(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.item = word;
}
public boolean search(String word) {
return match(word.toCharArray(), 0, root);
}
private boolean match(char[] chs, int k, TrieNode node) {
if (k == chs.length) return !node.item.equals("");
if (chs[k] != '.') {
return node.children[chs[k] - 'a'] != null && match(chs, k + 1, node.children[chs[k] - 'a']);
} else {
for (int i = 0; i < node.children.length; i++) {
if (node.children[i] != null) {
if (match(chs, k + 1, node.children[i])) {
return true;
}
}
}
}
return false;
}
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/211_Add_and_Search_Word_Data_Structure_Design.java
class TrieNode {
boolean finished;
TrieNode[] children;
TrieNode() {
finished = false;
children = new TrieNode[26];
}
}
TrieNode root;
/** 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 (char ch : word.toCharArray()) {
if (cur.children[ch - 'a'] == null)
cur.children[ch - 'a'] = new TrieNode();
cur = cur.children[ch - 'a'];
}
cur.finished = 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, 0, word);
}
private boolean searchHelper(TrieNode root, int index, String word) {
if (index == word.length()) return root.finished;
char ch = word.charAt(index);
if (ch != '.') {
if (root.children[ch - 'a'] == null) return false;
return searchHelper(root.children[ch - 'a'], index + 1, word);
} else {
for (int i = 0; i < 26; i ++)
if (root.children[i] != null)
if (searchHelper(root.children[i], index + 1, word))
return true;
return false;
}
}
follow up是虽然这个已经是optimal的⽅法,有没有可能让search更更快⼀一
点,表示在insert的时候就把“.”也当做⼀一个node加进去,⽐比如如果insert
“cat”, 那么第⼀一 层就是 “c”,".",第⼆二层是“a”,"." | "a","."
讨论:这道题有个很好的Follow up,就是当搜索的单词中存在星号怎么搞,星号的定义和Wildcard Matching中一样,可以代表任意的字符串,包括空字符串,请参见评论区1楼
if
(word[i] ==
'*'
) {
if
(i + 1 == word.size())
return
true
;
for
(
auto
&a : p->child) {
if
(a && (a->child[word[i + 1] -
'a'
] || word[i + 1] ==
'.'
|| word[i + 1] ==
'*'
) && searchWord(word, a, i + 1))
return
true
;
if
(a && searchWord(word, a, i))
return
true
;
}
return
false
;
}