JavaScript递归查找包含shiny gold bag的行李袋 代码小数据集可用大数据集失效

代码在大数据集下失效的原因 #

核心有3个问题：

• 循环内覆盖临时结果：do代码块中遍历colors数组时，每次迭代都会直接给tempCol赋值，前一次循环的查询结果会被完全覆盖，只有最后一个颜色对应的查询结果会被保留。你的测试小样例每轮colors数组的查询结果刚好一致，所以没有暴露问题，大数据集下多节点查询必然丢失大量结果。
• 未做去重处理：同一个父袋子如果可以通过多条路径装下shiny gold bag，会被重复加入colorsMain数组，最终统计的长度和实际结果不符。
• 模糊匹配存在潜在风险：用includes匹配袋子颜色，可能出现短字符串匹配长字符串的误判问题，例如存在shiny gold silver这类颜色时会被错误识别。

更高效的技术方案 #

推荐使用反向邻接表+BFS遍历的方案，时间复杂度为O(n)，600行数据可以毫秒级完成计算，逻辑清晰不易出错。
实现代码如下：

const input = `light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.`;

// 构建反向邻接表：key是子袋颜色，value是所有直接包含该子袋的父袋集合
const parentMap = new Map();
input.split('\n').map(line => line.trim()).forEach(line => {
  const [parentColor, childrenPart] = line.split(' bags contain ');
  if (childrenPart === 'no other bags.') return;
  childrenPart.split(', ').forEach(childStr => {
    // 精准提取子袋颜色，去掉数量、bag/bags后缀和标点
    const childColor = childStr.replace(/^\d+ /, '').replace(/ bags?\.?$/, '');
    if (!parentMap.has(childColor)) parentMap.set(childColor, new Set());
    parentMap.get(childColor).add(parentColor);
  });
});

// BFS遍历所有可以装下shiny gold的父袋
const targetBags = new Set();
const queue = ['shiny gold'];
while (queue.length) {
  const currentColor = queue.shift();
  const parents = parentMap.get(currentColor) || [];
  for (const p of parents) {
    if (!targetBags.has(p)) {
      targetBags.add(p);
      queue.push(p);
    }
  }
}

// 输出结果：targetBags就是所有符合要求的袋子数组，size是数量
console.log([...targetBags], targetBags.size);

该方案在小样例下输出结果为["bright white", "muted yellow", "light red", "dark orange"]，长度为4，和预期结果一致。

内容的提问来源于stack exchange，提问作者ranran212