我正在尝试以较低的时间复杂度解决问题,在本例中为 O(n)
。
问题是:
let arr = ['dog', 'come', 'ogd', 'something', 'emoc'];
它应该返回
[['dog', 'ogd], ['come', 'emoc']]; // which same using letters
到目前为止,我使用两个函数解决了这个问题,它工作得很好,但我的嵌套循环会给我 O(n2)
这是我的代码
const isSameChars = (str1, str2) => {
let str1sorted = str1.split("").sort().join("");
let str2sorted = str2.split("").sort().join("");
if (str1.length !== str2.length) {
return false;
}
for (var i = 0; i < str1sorted.length; i++) {
let char1 = str1sorted[i];
let char2 = str2sorted[i];
if (char1 !== char2) {
return false;
}
}
return true;
}
const isSameCharElements = (arr) => {
let result = [];
for(var i = 0; i < arr.length; i++) {
for(var j = 0; j < i; j++) {
if (isSameChars(arr[i], arr[j]) === true) {
result.push(arr[j])
}
}
}
return result;
}
console.log(isSameCharElements(['dog', 'come', 'ogd', 'something',
'emoc'])) // [['dog', 'ogd], ['come', 'emoc']]
有什么方法可以用 O(n)
的时间复杂度来解决这个问题吗?
谢谢你的预付款!
最佳答案
您可以通过对字母进行排序来获得任何字符串的“字母袋”表示形式:
function sortLetters(word){
return word.split('').sort().join('');
}
然后您可以遍历您的输入,将具有相同字母袋表示的单词分组到一个对象中:
const grouped = arr.reduce(function (m, word) {
var bagRepr = sortLetters(word);
var withSameLetters = m[bagRepr] || [];
withSameLetters.push(word);
m[bagRepr] = withSameLetters;
return m;
}, {});
const result = Object.values(grouped)
.filter(function (arr) {
return arr.length > 1;
});
这是 O(n),前提是 sortLetters()
是 O(1),如果单词长度受常数限制,情况就是如此。
免责声明:请注意,我们在这里只讨论渐近复杂性 - 这根本不意味着从实际 Angular 来看,这种方法是最有效的!
关于javascript - 如何在 javascript 中返回具有 O(n) 时间复杂度的相同字母元素?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50163007/