Closed congr closed 5 years ago
class WordDictionary {
WordDictionary[] child = new WordDictionary[128]; // !!!
boolean isLeaf;
/** Initialize your data structure here. */
public WordDictionary() {
}
/** Adds a word into the data structure. */
public void addWord(String word) {
addWord(word, 0);
}
private void addWord(String s, int p) {
if (s.length() == p) {
isLeaf = true; // !!!
return;
}
int ind = s.charAt(p);
if (child[ind] == null) child[ind] = new WordDictionary();
child[ind].addWord(s, p+1);
}
/** 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);
}
private boolean search(String s, int p) {
if (s.length() == p) return isLeaf; // !!!
int ind = s.charAt(p);
if (child[ind] != null) return child[ind].search(s, p+1);
boolean found = false;
if (s.charAt(p) == '.') {
for (WordDictionary w : child) {
if (w != null) found |= w.search(s, p+1); // !!!! |= merge result
}
}
return found;
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
https://leetcode.com/problems/add-and-search-word-data-structure-design/