时间戳

首页 > 解决方案 > 为什么我的 JavaScript 对于这个 Scrambles 任务来说太慢了？

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

问题描述

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

完成函数 scramble(str1, str2)，如果 str1 字符的一部分可以重新排列以匹配 str2，则返回 true，否则返回 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);
}

标签： javascript

解决方案

您的代码没有任何问题，只是通过最后一个测试太慢了。

代码中最慢的部分是排序。通过创建一个在单字符键下具有该字符数量的对象（例如，“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.

推荐阅读