Add and Search Word - Data structure design (M)
题目
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 a-z.
题意
设计一个数据结构，支持插入单词和搜索单词两个操作。其中，搜索单词的参数可以是一个包含通配符"."的正则。
思路
和 0208. Implement Trie (Prefix Tree) (M) 一样使用字典树。不同之处在于当搜索字符为"."时，要查找所有出现过的字母。
代码实现
Java
class WordDictionary {
Node root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new Node();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
Node p = root;
for (char c : word.toCharArray()) {
if (p.children[c - 'a'] == null) {
p.children[c - 'a'] = new Node();
}
p = p.children[c - 'a'];
}
p.end = 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 search(word, 0, root);
}
private boolean search(String word, int index, Node p) {
if (index == word.length()) {
return p.end;
}
char c = word.charAt(index);
if (c == '.') {
for (Node next : p.children) {
if (next != null && search(word, index + 1, next)) {
return true;
}
}
return false;
} else {
return p.children[c - 'a'] != null ? search(word, index + 1, p.children[c - 'a']) : false;
}
}
}
class Node {
Node[] children = new Node[26];
boolean end;
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary(); obj.addWord(word); boolean param_2
* = obj.search(word);
*/
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
