LeetCode - Design Add and Search Words Data Structure - C++

Let's discuss ⬇️

[lansicus]

struct TrieNode {
TrieNode *children[26];
bool isWord;

TrieNode() {
for (auto &c : children) { c = nullptr; }
isWord = false;
}
};

class WordDictionary {
private:
TrieNode *root;

void clear(TrieNode *tn) {
for (int i = 0; i < 26; i++) {
if (tn->children[i]) { clear(tn->children[i]); }
}
delete tn;
}

bool dfs(TrieNode *tn, string &s, int pos) {
// TC: O(26^(min(n, h)), SC: O(min(n, h), n = length of word, h = height of tree
if (pos == s.size()) { return tn->isWord; }
if (s[pos] != '.') {
tn = tn->children[s[pos] - 'a'];
if (!tn) { return false; }
return dfs(tn, s, pos + 1);
}
else {
for (int i = 0; i < 26; i++) {
if (tn->children[i] && dfs(tn->children[i], s, pos + 1)) {
return true;
}
}
return false;
}
}

public:
WordDictionary() {
// overall data structure SC: O(M * N) M = avg length of word, N = total words
root = new TrieNode();
}

~WordDictionary() {
this->clear(root);
}

void addWord(string word) {
// TC: O(n), SC: O(1)
TrieNode *tn = root;
for (auto &c : word) {
if (!tn->children[c - 'a']) {
tn->children[c - 'a'] = new TrieNode();
}
tn = tn->children[c - 'a'];
}
tn->isWord = true;
}

bool search(string word) {
return dfs(root, word, 0);
}
};