Solution
We could solve this question easily using a map if the special character . were not there. As a . can represent any character a-z, we’ll have to employ a different technique. This is a standard implementation of Trie with an updated Search function which employs backtracking to deal with the special character.
class WordDictionary {
private:
struct TrieNode {
bool isWord;
TrieNode *children[26];
TrieNode() {
isWord = false;
memset(children, NULL, sizeof(children));
}
};
TrieNode *root = NULL;
// helper function which employs backtracking to deal with the special character `.`
// searches for word starting from index idx in a Trie starting from given root
bool searchHelper (string word, int idx, TrieNode *root) {
if (root == NULL)
return false;
for (int i=idx; i<word.size(); i++) {
if (word[i] == '.') { // deal with special character
bool ans = false;
for (int j=0; j<26; j++) {
ans = ans || searchHelper(word, i+1, root->children[j]); // replace `.` with all chars a-z and see if we can find a solution for remaining word
}
return ans;
}
if (root->children[word[i]-'a'] == NULL)
return false;
root=root->children[word[i]-'a'];
}
return root->isWord;
}
public:
/** Initialize your data structure here. */
WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
void addWord(string word) {
TrieNode *temp = root;
for (char c : word) {
if(!temp->children[c-'a']) {
temp->children[c-'a'] = new TrieNode();
}
temp=temp->children[c-'a'];
}
temp->isWord = true;
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
bool search(string word) {
return searchHelper(word, 0, root);
}
};