优化嵌套循环实现：判断礼物是否可由给定材料制作

问题需求 #

给定礼物列表（字符串数组）和可用材料（字符串），返回所有可制作的礼物——礼物的所有字符都需在材料中存在（部分测试会验证字符出现次数是否足够）。

原代码分析 #

你的实现通过了大部分基础测试，但未通过秘密测试，核心问题在于未考虑字符出现次数的限制：当礼物需要多个相同字符，但材料中该字符的数量不足时，原代码会误判为可制作。此外，循环逻辑存在冗余，中断内层循环的方式不够优雅。

原代码：

function manufacture(gifts, materials) {
  // Code here
  const result = [];

  for(let i=0; i < gifts.length; i++) {
    for(let j=0; j < gifts[i].length; j++) {
        if (materials.includes(gifts[i][j])) {
          if(j === gifts[i].length -1) {
            result.push(gifts[i]);
          }
        } else {
          j = gifts[i].length;
        }
    }
     if (i === gifts.length -1) {
      return result;
    }
  }
  return [];
}

优化方案 #

方案一：考虑字符出现次数（解决秘密测试问题） #

先统计材料中每个字符的出现次数，再逐个验证礼物的字符需求是否被满足，这是最严谨的实现方式，能覆盖所有测试场景。

function manufacture(gifts, materials) {
  // 统计材料中每个字符的出现次数
  const materialCharCount = {};
  for (const char of materials) {
    materialCharCount[char] = (materialCharCount[char] || 0) + 1;
  }

  return gifts.filter(gift => {
    // 复制材料计数，避免修改原对象影响后续礼物的判断
    const tempCount = {...materialCharCount};
    for (const char of gift) {
      // 若字符不存在或剩余数量为0，说明无法制作该礼物
      if (!tempCount[char]) {
        return false;
      }
      tempCount[char]--;
    }
    return true;
  });
}

方案二：仅验证字符存在性（高效基础版） #

如果题目默认不限制字符出现次数（仅需字符存在），可以用Set优化查找效率（Set.has()的时间复杂度为O(1)，远优于String.includes()的O(n)），同时用数组方法简化代码：

function manufacture(gifts, materials) {
  const materialSet = new Set(materials);
  // 用every判断礼物的所有字符都在材料集合中
  return gifts.filter(gift => [...gift].every(char => materialSet.has(char)));
}

优化亮点 #

• 效率提升：用Set或对象存储材料字符，将字符查找的时间复杂度从O(n)降至O(1)，处理大规模数据时优势明显。
• 逻辑严谨：方案一覆盖了字符出现次数的场景，解决了秘密测试的核心问题。
• 代码简洁：使用数组的filter和every方法，符合函数式编程风格，可读性更强。
• 避免冗余：移除了原代码中多余的循环终止判断，用更清晰的逻辑中断验证流程。

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