Codewars Javascript Problem - 我的代码与双 for 循环超时

Question

我正在尝试解决Codewars上的一个问题，其中包括查看一个字符串是否包含第二个字符串中的所有字母。我想我已经找到了一个不错的解决方案，但我的代码超时(12000 毫秒(，我不知道为什么。谁能对这个问题有所了解？

function scramble(str1, str2) {
let i;
let j;
let x = str2.split();
for (i = 0; i < str1.length; i++) {
for (j = 0; j < str2.length; j++) {
if (str1[i] == str2[j]) {
x.splice(j, 1);
j--;
}
}
}
if (x.length == 0) {
return true;
} else {
return false;
}
}

Answer 1

如果你的字符串大小为 N 和 M，那么你的算法是 O(N*M(。您可以通过对两个字符串进行排序来获得 O(NlogN + MlogM(，然后进行简单的比较。但是你可以做得更好，通过计算一个字符串中的字母，然后看看它们是否存在于另一个字符串中，得到O(N+M(。例如，像这样：

function scramble(str1, str2) {
let count = {}
for (const c of str1) {
if (!count[c])
count[c] = 1
else
count[c]++
}
for (const c of str2) {
if (!(c in count))
return false
count[c]--
}
for (let k in count) {
if (count.hasOwnProperty(k) && count[k] !== 0)
return false
}
return true
}

Answer 2

您通过递增和递减j创建了一个无限循环。每当str1[i] == str2[j]，j的价值就会卡住

将代码片段简化为最简单的形式将如下所示：

for (j = 0; j < 10; j++) {
j--;
console.log(j) // always -1
}

Answer 3

您正在调整x但随后引用str2，就好像它已被更改一样。因为你从不调整str2，你总是在比较相同的两个字母，所以你陷入了一个循环。这是一个问题。然后，您问题的措辞表明我们正在检查str2中的每个字母是否都是str1，但您正在检查str1中的每个字母并将其与str2进行检查。str1应该是内部循环。

function scramble(str1, str2) {
var x = str2.split("");
for (var i = 0; i < x.length; i++) {
for (var j = 0; j < str1.length; j++) {
if (str1[j] == x[i]) {
x.splice(i--, 1);
}
}
}
return x.length === 0;
}
console.log(scramble("dirty rooms", "dormitory"));
console.log(scramble("cat", "dog"));

因为x.length === 0已经是一个布尔值，所以你可以只返回它。那里不需要 if 语句。三等号检查变量的类型和值，双等号仅检查值。当我检查 0 和 1 时，我倾向于总是使用三重，因为您不希望出现这样的意外后果：

console.log(false == 0, true == 1);
console.log(false === 0, true === 1);

另外，由于i--的意思是"执行后i = i - 1"，因此您可以将其直接放在对splice的调用中，并且在splice完成后才会执行。 另一方面，--i将在执行前进行评估。

这一切都很棒，但使用indexOf是一个更简单的解决方案：

function scramble(str1, str2) {
for (let i = 0; i < str2.length; i++) {
if (str1.indexOf(str2[i]) == -1) return false;
}
return true;
}
console.log(scramble("forty five", "over fifty"));
console.log(scramble("cat", "dog"));