Open huimeich opened 8 years ago
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.
For 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.
public class WordDictionary {
public class TrieNode {
HashMap<Character, TrieNode> childList;
boolean hasWord;
public TrieNode(){
childList = new HashMap<Character, TrieNode>();
hasWord = false;
}
}
TrieNode root;
public WordDictionary() {
root = new TrieNode();
}
// Adds a word into the data structure.
public void addWord(String word) {
TrieNode temp = root;
for (int i = 0; i < word.length(); i++){
Character c = new Character(word.charAt(i));
if (temp.childList.get((Character)c) == null) {
temp.childList.put(c, new TrieNode());
}
temp = temp.childList.get(c);
if (i == word.length() - 1) temp.hasWord = 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, root);
}
public boolean search(String word, TrieNode trie) {
TrieNode temp = trie;
for (int i = 0; i < word.length(); i++){
Character c = new Character(word.charAt(i));
if (c.charValue() != '.') {
if (temp.childList.get(c) == null) return false;
temp = temp.childList.get(c);
} else {
for (TrieNode j : temp.childList.values()) {
if (i == word.length() - 1) {
if (j.hasWord) return true;
} else if ( search(word.substring(i + 1), j) ) {
return true;
}
}
return false;
}
}
return temp.hasWord;
}
}
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");
Implement a trie with insert, search, and startsWith methods.
Note: You may assume that all inputs are consist of lowercase letters a-z.