LeetCode 1268. 搜索推荐系统

Categories:

题目描述
思路分析
1. 解法一：排序 + 二分（推荐）
相似题目

题目描述

✅ 1268. 搜索推荐系统

思路分析

解法一：排序 + 二分（推荐）

核心思路：

将产品数组按字典序排序。

对每个前缀，用二分找到第一个可能匹配的位置。

从该位置取最多 3 个匹配项作为推荐。

复杂度分析：

时间复杂度：O(m log n + m * 3)，其中 n 为产品数，m 为搜索词长度。

空间复杂度：O(1)（不计输出结果）。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        List<List<String>> res = new ArrayList<>();

        String prefix = "";
        for (int i = 0; i < searchWord.length(); i++) {
            prefix += searchWord.charAt(i);
            int start = lowerBound(products, prefix);

            List<String> list = new ArrayList<>();
            for (int k = start; k < products.length && list.size() < 3; k++) {
                if (products[k].startsWith(prefix)) {
                    list.add(products[k]);
                } else {
                    break;
                }
            }
            res.add(list);
        }

        return res;
    }

    private int lowerBound(String[] arr, String target) {
        int left = 0;
        int right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid].compareTo(target) >= 0) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

import "sort"

func suggestedProducts(products []string, searchWord string) [][]string {
	sort.Strings(products)
	res := make([][]string, 0)

	prefix := ""
	for i := 0; i < len(searchWord); i++ {
		prefix += string(searchWord[i])
		start := lowerBound(products, prefix)

		list := make([]string, 0)
		for k := start; k < len(products) && len(list) < 3; k++ {
			if len(products[k]) >= len(prefix) && products[k][:len(prefix)] == prefix {
				list = append(list, products[k])
			} else {
				break
			}
		}
		res = append(res, list)
	}

	return res
}

func lowerBound(arr []string, target string) int {
	left, right := 0, len(arr)
	for left < right {
		mid := left + (right-left)/2
		if arr[mid] >= target {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

相似题目

题目	难度	考察点
1268. 搜索推荐系统	中等	排序、二分
208. 实现 Trie (前缀树)	中等	Trie
211. 添加与搜索单词 - 数据结构设计	中等	Trie
642. 设计搜索自动补全系统	困难	Trie
648. 单词替换	中等	Trie

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/60401575