Design Add and Search Words Data Structure

How it works

The simplest way to solve this problem is to store all words as-is and check every stored word during search.

When searching:

• If the lengths don't match → it can't be a match.
• Compare characters one by one:
  • Exact match is required unless the search character is .
  • . acts as a wildcard and can match any character.

This approach works because the constraints are small enough, but it is not efficient for large datasets.

Steps

Data Structure

• Maintain a list to store all added words.

---

addWord(word)

1. Append the word to the list.

---

search(word)

1. Loop through every stored word:
   • Skip if lengths differ.
2. Compare characters index by index:
   • If characters match → continue.
   • If search character is . → treat as match.
   • Otherwise → stop checking this word.
3. If all characters match → return true.
4. If no word matches → return false.

Complexity

• Time complexity: O(1) for addWord(), O(m * n) for search().
• Space complexity: O(m * n)

Where m is the number of words added and n is the length of the string.

Things to watch for

Returning True at Any Node Instead of Word-End Nodes

When the search reaches the end of the pattern, you must check if the current node marks the end of a valid word, not just that the node exists. A prefix match is not the same as a word match.

Not Exploring All Children for Wildcard

When encountering a . wildcard, you must try all possible children nodes. A common mistake is returning after the first child or not iterating through all 26 possible characters.

Confusing Node Existence with Word Existence

When a character is not found in the Trie, return False immediately. However, when using wildcards, absence of any children should also return False, but only after checking all possibilities.

class WordDictionary:

    def __init__(self):
        self.store = []

    def addWord(self, word: str) -> None:
        self.store.append(word)

    def search(self, word: str) -> bool:
        for w in self.store:
            if len(w) != len(word):
                continue
            i = 0
            while i < len(w):
                if w[i] == word[i] or word[i] == '.':
                    i += 1
                else:
                    break
            if i == len(w):
                return True
        return False

class WordDictionary {
public:
    vector<string> store;

    WordDictionary() {}

    void addWord(string word) {
        store.push_back(word);
    }

    bool search(string word) {
        for (string w : store) {
            if (w.length() != word.length()) continue;
            int i = 0;
            while (i < w.length()) {
                if (w[i] == word[i] || word[i] == '.') {
                    i++;
                } else {
                    break;
                }
            }
            if (i == w.length()) {
                return true;
            }
        }
        return false;
    }
};