脚本宝典收集整理的这篇文章主要介绍了[LeetCode] 211. Add and Search Word - Data structure design，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
Problem
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.
Solution
class WordDictionary {
public class TrieNode {
public TrieNode[] children = new TrieNode[26];
public boolean isWord = false;
}
TrieNode root = new TrieNode();
public void addWord(String word) {
TrieNode node = root;
for (char ch: word.toCharArray()) {
if (node.children[ch-'a'] == null) {
node.children[ch-'a'] = new TrieNode();
}
node = node.children[ch-'a'];
}
node.isWord = true;
}
public boolean search(String word) {
return helper(word, 0, root);
}
private boolean helper(String word, int start, TrieNode node) {
if (start == word.length()) return node.isWord;
char ch = word.charAt(start);
if (ch == '.') {
for (int i = 0; i < 26; i++) {
if (node.children[i] != null && helper(word, start+1, node.children[i])) {
return true;
}
}
} else {
return node.children[ch-'a'] != null && helper(word, start+1, node.children[ch-'a']);
}
return false;
}
}
以上是脚本宝典为你收集整理的[LeetCode] 211. Add and Search Word - Data structure design全部内容，希望文章能够帮你解决[LeetCode] 211. Add and Search Word - Data structure design所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。