时间戳

首页 > 解决方案 > 如何在javascript中返回具有O(n)时间复杂度的相同字母元素？

javascript - 如何在javascript中返回具有O(n)时间复杂度的相同字母元素？

问题描述

我正在尝试解决时间复杂度较低的问题，在这种情况下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)时间复杂度问题？

谢谢你的提前！

标签： javascriptalgorithmtime-complexity

解决方案

您可以通过对字母进行排序来获得任何字符串的“字母袋”表示：

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)，如果单词长度受一个常数限制，就会出现这种情况。

免责声明：请注意，我们在这里只讨论渐近复杂性 - 这并不意味着从实际角度来看这种方法是最有效的！

推荐阅读