解題程式碼

var WordDictionary = function () {
  this.root = {};
};

/**
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function (word) {
  let node = this.root;
  for (let c of word) {
    if (!node[c]) node[c] = {};
    node = node[c];
  }
  node.isEnd = true;
};

/**
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function (word) {
  const dfs = (index, node) => {
    if (word.length === index) return !!node.isEnd;

    // 碰到 '.'，就往下找 trie 裡面有沒有 word 的下一個字元
    if (word[index] === '.') {
      for (let key in node) {
        if (dfs(index + 1, node[key])) return true;
      }
      // not found，return false;
    } else {
      if (node[word[index]]) {
        return dfs(index + 1, node[word[index]]);
      }
      // not found，return false;
    }
    return false;
  };

  return dfs(0, this.root);
};

解題思路、演算法

這題使用 Trie + DFS 實作，在 search 的部分，分成碰到 '.' 和碰到字元的情況做處理。

解法的時間、空間複雜度

時間複雜度: addWord: O(s)，s 為每次加入 word 的長度，search: O(26^s)，s 為每次搜尋 word 的長度
空間複雜度: O(t * 26)，t 為所有 addWord() 加入的 word 長度和，26 為全部小寫英文字母

參考資料

Design Add and Search Words Data Structure - Leetcode 211 - Python