Add and Search Word with Regular Expression - Data structure design
Add and Search Word with Regular Expression - Data structure design
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 . or * . A . means it can represent any one letter. A * can be any sequence of characters (including the empty sequence).
For example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Thoughts
empty意味着i+1但node不往后走, any other sequence意味着node可以跳过任意次, 再和i + 1匹配.
Code
class WordDictionary {
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean end;
}
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 node = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.end = true;
}
private boolean dfs(String word, TrieNode node, int pos) {
for (int i = pos; i < word.length(); i++) {
if (word.charAt(i) == '.') {
for (int j = 0; j < 26; j++) {
if (node.children[j] != null) {
if (dfs(word, node.children[j], i + 1)) {
return true;
}
}
}
return false;
} else if (word.charAt(i) == '*') {
// be any seq of characters, including empty
for (int j = 0; j < 26; j++) {
if (node.children[j] != null) {
if (dfs(word, node.children[j], i) // skip nodes: acccb(node), a*(pos)b skip ccc
|| dfs(word, node.children[j], i + 1) // jump to next character, a*b(pos), acccb(node)
|| dfs(word, node, i + 1)) { // skip *: empty a(node)b, a*(pos)b => a(node)b, a*b(pos)
return true;
}
}
}
return false;
} else {
int index = word.charAt(i) - 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
}
return node.end;
}
/** 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 dfs(word, root, 0);
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/