1268. Search Suggestions System

Medium
Description

給定產品名稱陣列 products 和搜尋字串 searchWord。每輸入一個字元後，回傳最多 3 個字典序最小的匹配產品（以當前已輸入的前綴開頭）。

Example:

Input: products = [“mobile”,“mouse”,“moneypot”,“monitor”,“mousepad”], searchWord = “mouse” Output: [[“mobile”,“moneypot”,“monitor”],[“mobile”,“moneypot”,“monitor”],[“mouse”,“mousepad”],[“mouse”,“mousepad”],[“mouse”,“mousepad”]]

Intuition#

排序後用二分搜尋找每個前綴的起始位置，取最多 3 個匹配結果。

  • 排序後，相同前綴的產品會聚在一起
  • 對每個前綴，用二分搜尋找到第一個 >= 前綴的位置
  • 從該位置開始取最多 3 個匹配的產品

Approaches#

1: 排序 + 暴力匹配#

  • 概念: 排序後，對每個前綴遍歷所有產品找匹配
  • 時間複雜度: O(n log n + m * n * L)，n = 產品數，m = searchWord 長度，L = 平均產品名長度
  • 空間複雜度: O(1)（不計結果）
暴力匹配程式碼
class Solution {
    fun suggestedProducts(products: Array<String>, searchWord: String): List<List<String>> {
        products.sort()
        val result = mutableListOf<List<String>>()
        for (i in 1..searchWord.length) {
            val prefix = searchWord.substring(0, i)
            val matches = mutableListOf<String>()
            for (product in products) {
                if (product.startsWith(prefix) && matches.size < 3) {
                    matches.add(product)
                }
            }
            result.add(matches)
        }
        return result
    }
}

⭐2: Sort + Binary Search#

  • 概念: 排序後，對每個前綴用二分搜尋找起始位置，取最多 3 個匹配
  • 時間複雜度: O(n log n + m * log n * L)
  • 空間複雜度: O(1)（不計結果和排序空間）
class Solution {
    fun suggestedProducts(products: Array<String>, searchWord: String): List<List<String>> {
        products.sort()
        val result = mutableListOf<List<String>>()
        var prefix = ""
        for (ch in searchWord) {
            prefix += ch
            // 二分搜尋找第一個 >= prefix 的位置
            var lo = 0
            var hi = products.size
            while (lo < hi) {
                val mid = lo + (hi - lo) / 2
                if (products[mid] < prefix) {
                    lo = mid + 1
                } else {
                    hi = mid
                }
            }
            val matches = mutableListOf<String>()
            for (i in lo until minOf(lo + 3, products.size)) {
                if (products[i].startsWith(prefix)) {
                    matches.add(products[i])
                } else {
                    break
                }
            }
            result.add(matches)
        }
        return result
    }
}

3: Trie#

  • 概念: 建立 Trie，每個節點存最多 3 個字典序最小的產品
  • 時間複雜度: O(n * L + m)（建 Trie + 查詢）
  • 空間複雜度: O(n * L)（Trie 空間）
Trie 程式碼
class Solution {
    class TrieNode {
        val children = arrayOfNulls<TrieNode>(26)
        val suggestions = mutableListOf<String>()
    }

    fun suggestedProducts(products: Array<String>, searchWord: String): List<List<String>> {
        products.sort()
        val root = TrieNode()
        for (product in products) {
            var node = root
            for (ch in product) {
                val idx = ch - 'a'
                if (node.children[idx] == null) {
                    node.children[idx] = TrieNode()
                }
                node = node.children[idx]!!
                if (node.suggestions.size < 3) {
                    node.suggestions.add(product)
                }
            }
        }
        val result = mutableListOf<List<String>>()
        var node: TrieNode? = root
        for (ch in searchWord) {
            node = node?.children?.get(ch - 'a')
            result.add(node?.suggestions ?: emptyList())
        }
        return result
    }
}

🔑 Takeaways#

  • Pattern: 排序 + 二分搜尋 / Trie 前綴搜尋
  • 關鍵技巧: 排序後相同前綴會聚在一起，二分搜尋找到起始位置後只需檢查最多 3 個。Trie 解法在多次查詢時更高效，但實作較複雜