Question
Formatted question description: https://leetcode.ca/all/211.html
211. Add and Search Word - 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 .. 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
Constraints:
1 <= word.length <= 500
word in addWord consists lower-case English letters.
word in search consist of '.' or lower-case English letters.
At most 50000 calls will be made to addWord and search.
Algorithm
With the structure of the Trie
, the only difference is that the search function needs to be rewritten, compared with Trie problem.
Because the .
in this question can replace any character, once there is a .
, all subtrees need to be searched. As long as one returns true, the entire search function returns true.
Typical DFS problem.
Code
Java
public class Add_and_Search_Word_Data_structure_design {
class WordDictionary {
Trie trie;
/** Initialize your data structure here. */
public WordDictionary() {
trie = new Trie();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
trie.insert(word);
}
/** 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 trie.search(word);
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
class TrieNode {
// R children to node children
public TrieNode[] children;
private final int R = 26;
private boolean isEnd;
public TrieNode() {
children = new TrieNode[R];
}
public boolean containsKey(char ch) {
return children[ch -'a'] != null;
}
public TrieNode get(char ch) {
return children[ch -'a'];
}
public void put(char ch, TrieNode node) {
children[ch -'a'] = node;
}
public void setEnd() {
isEnd = true;
}
public boolean isEnd() {
return isEnd;
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
TrieNode node = root;
// @note:@memorize: iteration is better than recursion during trie building
for (int i = 0; i < word.length(); i++) {
char currentChar = word.charAt(i);
if (!node.containsKey(currentChar)) {
node.put(currentChar, new TrieNode());
}
node = node.get(currentChar);
}
node.setEnd();
}
// search a prefix or whole key in trie and
// returns the node where search ends
public boolean search(String word) {
return dfs(word, root);
}
private boolean dfs(String word, TrieNode node) {
if (node == null) {
return false;
}
if (word.length() == 0) {
return node.isEnd();
}
char curLetter = word.charAt(0);
if (curLetter == '.') {
for (int i = 0; i < 26; i++) {
char c = (char)('a' + i);
if (dfs(word.substring(1), node.get(c))) {
return true;
}
}
} else if (node.containsKey(curLetter)){
return dfs(word.substring(1), node.get(curLetter));
}
return false;
}
}
public class WordDictionary_bucket {
// bucket: word length -> list of words
Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();
// Adds a word into the data structure.
public void addWord(String word) {
int index = word.length();
if(!map.containsKey(index)){
List<String> list = new ArrayList<String>();
list.add(word);
map.put(index, list);
}else{
map.get(index).add(word);
}
}
// 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) {
int index = word.length();
if(!map.containsKey(index)){
return false;
}
List<String> list = map.get(index);
if(isWords(word)){
return list.contains(word);
}
for(String s : list){
if(isSame(s, word)){
return true;
}
}
return false;
}
boolean isWords(String s){
for(int i = 0; i < s.length(); i++){
// @note: api isLetter()
if(!Character.isLetter(s.charAt(i))){
return false;
}
}
return true;
}
boolean isSame(String a, String search){
if(a.length() != search.length()){
return false;
}
for(int i = 0; i < a.length(); i++){
if(search.charAt(i) != '.' && search.charAt(i) != a.charAt(i)){
return false;
}
}
return true;
}
}
}