CodeWars Scramblies挑战代码未通过测试，寻求修复方案

我正在解决CodeWars的Scramblies kata，需要实现scramble(str1, str2)函数——如果str1的部分字符可重排后匹配str2则返回true，否则返回false。仅使用小写字母，还要考虑性能。

我的代码在str2包含str1中没有足够数量的重复字符时测试失败，比如输入s1='scriptjavx'、s2='javascript'时返回错误结果。

原代码如下：

function scramble(str1, str2) {
  let sameChar = ""
  for (char of str2) {
    if (str1.includes(char)) {
      sameChar += char
    }
  }
  if (str2 == sameChar) 
    return true
  else
    return false;
}

问题根源 #

你的代码只检查了字符是否存在，没统计字符出现的次数。比如例子里str2有两个a，但str1只有一个a，你的代码依然会把两个a都加入sameChar，导致错误判断。

修复方案 #

核心思路是统计两个字符串中每个字符的出现次数，然后检查str2的每个字符的次数都不超过str1中的对应次数。

方案1：用对象统计字符频率（性能最优） #

function scramble(str1, str2) {
  const charCount = {};
  // 统计str1的每个字符出现次数
  for (const char of str1) {
    charCount[char] = (charCount[char] || 0) + 1;
  }
  // 遍历str2，逐一扣减对应字符的计数
  for (const char of str2) {
    if (!charCount[char] || charCount[char] === 0) {
      return false;
    }
    charCount[char]--;
  }
  return true;
}

方案2：修改原思路（直观但性能稍差） #

每次匹配到字符后，从str1的数组中移除该字符，避免重复使用：

function scramble(str1, str2) {
  let arr1 = str1.split('');
  for (const char of str2) {
    const matchIndex = arr1.indexOf(char);
    if (matchIndex === -1) {
      return false;
    }
    arr1.splice(matchIndex, 1);
  }
  return true;
}

性能对比 #

• 方案1的时间复杂度为O(n + m)（n是str1长度，m是str2长度），仅需两次遍历，适合处理大规模字符串。
• 方案2的时间复杂度为O(m * n)，因为indexOf和splice操作都会遍历数组，长字符串场景下性能会明显下降。

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