解題程式碼

Trie

var suggestedProducts = function (products, searchWord) {
  products.sort();
  const result = [];
  const trie = {};

  for (let i = 0; i < products.length; i++) {
    let curNode = trie;
    for (let c of products[i]) {
      if (!curNode[c]) curNode[c] = { suggest: [] };
      if (curNode[c]['suggest'].length < 3) curNode[c]['suggest'].push(products[i]);
      curNode = curNode[c];
    }
  }

  let root = trie;
  for (let i = 0; i < searchWord.length; i++) {
    if (root) root = root[searchWord[i]];
    result.push(root?.suggest ? root?.suggest : []);
  }

  return result;
};

二元搜尋

var suggestedProducts = function (products, searchWord) {
  products.sort();
  const result = [];
  let prefix = '';

  for (let i = 0; i < searchWord.length; i++) {
    const suggestion = [];
    prefix += searchWord[i];
    let l = 0;
    let r = products.length - 1;

    while (l <= r) {
      let mid = Math.floor((l + r) / 2);
      // ex: 'mca' < 'mcb'
      if (products[mid] >= prefix) {
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }

    for (let j = 0; j < 3; j++) {
      if (j + l < products.length && products[j + l].startsWith(prefix)) {
        suggestion.push(products[j + l]);
      }
    }

    result.push(suggestion);
  }
  return result;
};

暴力解

反而比第一個解更快 = =

var suggestedProducts = function (products, searchWord) {
  products.sort();
  let res = [];
  for (let i = 0; i < searchWord.length; i++) {
    products = products.filter((p) => p[i] == searchWord[i]);
    res.push(products.slice(0, 3));
  }
  return res;
};

解題思路、演算法

這題有不少的解法，可以用暴力解(測資不大)、二元搜尋優化，Two pointer，也可以用 Trie 解題。

解法的時間、空間複雜度

Trie

時間複雜度: O(n * log n) + O(n * m) + O(s)，n 為 products 數目，m 為 products 的平均長度，s 為 searchWord 長度
空間複雜度: O(n * m + s * 3)

參考資料

JavaScript Solution - Trie & Sort

挺好的想法，這樣每個字母節點都會有對應的建議關鍵字可以回傳

花花酱 LeetCode 1268. Search Suggestions System - 刷题找工作 EP268

二分搜尋法

Search Suggestions System - Leetcode 1268 - Python

使用 Two pointer