Design Add and Search Words Data Structure Medium 0 attempts
LeetCode ↗

Design Add and Search Words Data Structure

Medium Tries LeetCode

Design a data structure that supports adding new words and searching for a string where '.' can match any character.

Example: addWord("bad"), search("b.d") → true, search("b..") → true

Sample Input
—
Sample Output
—
Constraints
  • 1 <= word.length <= 25
  • word consists of lowercase letters or .
  • At most 10^4 calls to addWord and search
Topics
Tries

Trie with DFS for Wildcards

class WordDictionary {
  constructor() { this.root = {}; }
  addWord(word) {
    let node = this.root;
    for (const c of word) { if (!node[c]) node[c] = {}; node = node[c]; }
    node.$ = true;
  }
  search(word) {
    function dfs(node, i) {
      if (!node) return false;
      if (i === word.length) return !!node.$;
      if (word[i] === '.') return Object.keys(node).some(k => k !== '$' && dfs(node[k], i+1));
      return dfs(node[word[i]], i+1);
    }
    return dfs(this.root, 0);
  }
}

Time: addWord O(L), search O(26^L) worst | Space: O(total chars)

Saved in this browser only. Private to you.

JavaScript