gpt4 book ai didi

javascript - JavaScript Anagram 函数的时间复杂度

转载 作者:行者123 更新时间:2023-12-03 02:45:43 26 4
gpt4 key购买 nike

我有一个分配给一个函数,该函数将接受 2 个字符串并返回需要删除的字符数,以便使 2 个字符串彼此变位。我的问题是这个函数的时间复杂度是多少以及是否有更快的方法来达到相同的结果。这是我的解决方案:

function anagramDelete(str1, str2){
let obj1 = {}, obj2 = {};

// Load obj1 with all characters of str1 and their count
str1.split('').forEach((char)=> {
if(char in obj1){
obj1[char]++;
} else {
obj1[char] = 1;
}
});

// Load obj2 with all characters of str1 and their count
str2.split('').forEach((char)=> {
if(char in obj2){
obj2[char]++;
} else {
obj2[char] = 1;
}
});

// Track # of chars deleted
let numOfDeletions = 0;

// Compare each char in obj1 w obj2 and count deletions
for(char in obj1){
if(obj2[char]){
numOfDeletions += Math.abs(obj2[char] - obj1[char]);
} else {
numOfDeletions += obj1[char];
}
}
// Compare each char in obj2 w obj1 and count deletions
for(char in obj2){
if(!obj1[char]){
numOfDeletions += obj2[char];
}
}
return numOfDeletions;
}

据我所知,因为有 4 个循环,所以时间复杂度为 O(4n) 或 O(n)。我这样说是因为没有嵌套循环。它是否正确?还有更好的解决方案吗?

最佳答案

您可以使用单个对象并仅对绝对值求和。

此解决方案使用字符串作为类似数组的对象。

function anagramDelete(str1, str2) {
var letters = {};

Array.prototype.forEach.call(str1, char => letters[char] = (letters[char] || 0) + 1);
Array.prototype.forEach.call(str2, char => letters[char] = (letters[char] || 0) - 1);

return Object.keys(letters).reduce((r, k) => r + Math.abs(letters[k]), 0);
}

console.log(anagramDelete('anagram', 'function'));

关于javascript - JavaScript Anagram 函数的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48103093/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com