javascript - 为什么我的 JavaScript 对于这个 Scramblies 任务来说太慢了？

Question

我正在尝试解决以下任务:

Complete the function scramble(str1, str2) that returns true if a portion of str1 characters can be rearranged to match str2, otherwise returns false.

我编写的代码通过了初始测试，但在最终尝试时失败并出现以下错误:“执行超时(12000 毫秒)”。 这里有什么问题？

function scramble(str1, str2) {
   
let array1 = str1.split("").sort(); 
let array2 = str2.split("").sort();
let count = 0;
 
for(let a = 0; a <= array1.length && count < array2.length; a++) {
    if(array2[count] === array1[a]){
      count++;  
      }
  }
  
return (count === array2.length);
}

Answer 1

你的代码没有问题，只是速度太慢，无法通过上次测试。

代码中最慢的部分是排序。通过创建一个对象，该对象在一个字符键下具有该字符的数量(例如，“Hello world”变为 {"H": 1, "e": 1, "l": 3, "w": 1, "o": 2, "r": 1, "d": 1}。您可以使用这个“单行”函数在 O(n) 中做到这一点:

function getCharFrequencies(str) {
    return str.split("").reduce(
        function(container, char) {
            (container[char] += 1) || (container[char] = 1);
            return container;
        }, 
    {});
}

然后，您可以将每个字符串传递给该函数，并将 str2 中的所有字符频率与 str1 中的所有字符频率进行比较，以查看是否可以使 str2 来自 str1。