LeetCode 补充题 136. 多组键值选项的笛卡尔积

约 4 分钟
文章信息 4 个分类 1 个标签
分类
补充题 中等 腾讯 MiniMax
标签
回溯

题目描述

给你一个有序键列表 keys，以及与其一一对应的字符串选项列表 options。所有键互不重复。

请从每个键的选项中恰好选择一个值，返回全部可能的键值组合。

如果任意一个选项列表为空，返回空列表；如果没有键，返回只包含一个空组合的列表。

示例 1：

输入： keys = ["颜色","尺寸"], options = [["红","蓝"],["S","M"]]
输出： [{"颜色":"红","尺寸":"S"},{"颜色":"红","尺寸":"M"},{"颜色":"蓝","尺寸":"S"},{"颜色":"蓝","尺寸":"M"}]
解释： 每个键恰好选择一个选项，共 2×2=4 种组合。

提示：

  • keys 互不重复，options 与 keys 一一对应。
  • 每个键恰选一个选项。
  • 任何一组选项为空时无组合。
  • 没有键时返回一个空组合。

题意分析

每个键必须恰好选择一个选项，各组之间没有额外约束，所以结果是各组选项的笛卡尔积。需要枚举实际映射，输出数量本身就可能是各组长度的乘积。

解法：逐组选一个选项的回溯

核心思路

[!blue]

第 i 层只处理 keys[i]，进入时 path 已保存前 i 个键的选择。遍历当前组选项，将值写到该键后递归到下一层，所有组合都按固定键顺序产生，不依赖哈希表的遍历次序。

当 i == keys.size() 时，一条完整组合形成，必须复制当前映射再加入结果；否则后续覆盖和删除键会改变已保存的答案。当前层全部选项结束后移除自己的键，恢复调用前状态。

任意一组为空就无法完成选择，预检查后直接返回空列表；没有键时则立即到达叶子，保存一个空映射，符合空乘积的定义。

解题步骤

  1. 先检查是否有空选项组，有则直接返回空结果。
  2. 按固定键顺序递归，每层给当前键选择一个值。
  3. 全部键选完时复制映射，返回上一层后移除当前键。

代码实现

class Solution {
    public List<Map<String, String>> product(List<String> keys, List<List<String>> options) {
        List<Map<String, String>> out = new ArrayList<>();

        for (List<String> choices : options) {
            if (choices.isEmpty()) {
                return out;
            }
        }

        dfs(keys, options, 0, new LinkedHashMap<>(), out);

        return out;
    }

    private void dfs(
            List<String> keys,
            List<List<String>> options,
            int i,
            Map<String, String> path,
            List<Map<String, String>> out) {
        if (i == keys.size()) {
            out.add(new LinkedHashMap<>(path));

            return;
        }

        for (String value : options.get(i)) {
            path.put(keys.get(i), value);
            dfs(keys, options, i + 1, path, out);
        }

        path.remove(keys.get(i));
    }
}

func product(keys []string, options [][]string) []map[string]string {
    out := []map[string]string{}
    for _, choices := range options {
        if len(choices) == 0 {
            return out
        }
    }
    path := map[string]string{}
    var dfs func(int)
    dfs = func(i int) {
        if i == len(keys) {
            item := map[string]string{}
            for k, v := range path {
                item[k] = v
            }
            out = append(out, item)
            return
        }
        for _, value := range options[i] {
            path[keys[i]] = value
            dfs(i + 1)
        }
        delete(path, keys[i])
    }
    dfs(0)
    return out
}

复杂度分析

  • 时间复杂度：先用 $O(k)$ 检查是否存在空组选项，有则直接返回。各组非空时，组数为 k、组合数为 P，时间 $O(kP)$。
  • 空间复杂度：辅助空间 $O(k)$，结果空间 $O(kP)$；没有键时直接返回一个空组合。

关键点总结

[!green]

各组独立，非空时组合数为各组选项数的乘积；没有键的空乘积对应一个空组合。

易错点总结

[!yellow]

每条答案必须复制映射；选项中重复值按不同选择位置保留，若需要唯一组合应先对每组选项去重。

相似题目

题目 难度 关联与区别
17. 电话号码的字母组合 中等 每个数字对应一组选项，按层各选一个字母就是同样的笛卡尔积。
784. 字母大小写全排列 中等 把每个字符的大小写选项视为一组，本题推广为任意键与任意字符串选项。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/86327778
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！