Problem
Design a data structure that supports adding new words and finding if a string matches any previously added string.
Implement the WordDictionary class:
WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.
Example:
Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return 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.
Solution
The fastest word insert and retrieving datastructure we know so far is R-way trie. So lets do it.
import java.util.*;
class Solution {
public static void main(String...args) {
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
System.out.println(wordDictionary.search("pad")); // return False
System.out.println(wordDictionary.search("bad")); // return True
System.out.println(wordDictionary.search(".ad")); // return True
System.out.println(wordDictionary.search("b..")); // return True
System.out.println(wordDictionary.search("c..")); // return False
}
}
class WordDictionary {
private static class Node {
Node[] next = new Node[26];
boolean isEnd;
}
Node root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new Node();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
addNode(root, word, 0);
}
private void addNode(Node node, String word, int n) {
if(n == word.length())
return;
int pos = word.charAt(n) - 'a';
Node next = node.next[pos];
if(next == null) {
next = new Node();
node.next[pos] = next;
}
if(n == word.length() - 1) {
next.isEnd = true;
}
addNode(next, word, n+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(root, word, 0);
}
private boolean search(Node node, String word, int n) {
if(n == word.length())
return true;
char c = word.charAt(n);
if(c == '.') {
if(n == word.length() - 1) {
for(Node cur : node.next) {
if(cur != null && cur.isEnd) {
return true;
}
}
return false;
}
for(Node cur : node.next) {
if(cur != null && search(cur, word.substring(n+1), 0)) {
return true;
}
}
return false;
} else {
int pos = c - 'a';
Node next = node.next[pos];
if(next == null) {
return false;
} else {
if(n == word.length() - 1) {
return next.isEnd;
}
return search(next, word, n+1);
}
}
}
}
The time complexity for insert is O(w), where w is the word length. The space complexity for insert is O(w) we need to create w new node.
The time complexity for search hit a normal word is O(w), because we processed each character. The search miss for normal word is O(1) on average. The space complexity for search a normal word is O(w), which proportional to caller stack depth.
The time complexity for searching a . word is O(wN) where N is the number of keys in the dictionary. In the worst case an all .... search will exam all the possible pass in the dictionary. The space complexity is O(w) which is proportional to caller stack depth.
