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 lets you insert words one at a time and later check whether a given pattern matches any word you've stored, where a '.' in the pattern can stand in for any single character.

Input Format
Implement the class WordDictionary. Fixtures contain constructor arguments and a list of [method, ...arguments] calls. Each fixture starts with a fresh instance.
Output Format
Return the specified result from each method. The displayed output lists results in call order; undefined results appear as null.

Sample Input and Output

Example 1 ยท Run Sample

Input
constructorArgs = []
operations = [["addWord","bad"],["addWord","dad"],["search","pad"],["search","bad"],["search",".ad"],["search","b.."]]
Output
[null,null,false,true,true,true]

Example 2

Input
constructorArgs = []
operations = [["search","a"],["addWord","ab"],["search","."],["search",".."]]
Output
[false,null,false,true]
Constraints
  • 1 <= word.length <= 25
  • addWord accepts lowercase letters only; search additionally accepts dot wildcards.
  • At most 10^4 calls.
Test Cases (2)
Case 1
Args: [[],[["addWord","bad"],["addWord","dad"],["search","pad"],["search","bad"],["search",".ad"],["search","b.."]]] Expected: [null,null,false,true,true,true]
Case 2
Args: [[],[["search","a"],["addWord","ab"],["search","."],["search",".."]]] Expected: [false,null,false,true]
Topics
Tries

Trie with DFS for Wildcards

javascript
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