检查两个字符串是否是字谜的运行时间应该是多少

Question

我写了这个函数，我认为运行时间是 O(nlogN)，但我不确定。另外，有没有更干净的方法来写这个（java）？我觉得更有经验的程序员可以用更少的代码行来做到这一点。

public static boolean anagramCheck(String strA, String strB){
  if(strA.length() != strB.length()){
  return false;
}

char arrA[] = strA.toCharArray();
char arrB[] = strB.toCharArray();

Arrays.sort(arrA);
Arrays.sort(arrB);

int j = 0;
for(char s : arrA){
    if(s != arrB[j]){
        return false;
    }
     j++;
  }
    return true;
}

Answer 1

排序相对昂贵 - O(n log n) - 通常应尽可能避免。

您可以通过遍历每个字符串来收集字符频率，从而将时间复杂度降低到 O(n)，然后可以使用 Map#equals.

进行比较

只需一行即可完成：

return strA.chars().boxed().collect(Collectors.groupingBy(i -> i, Collectors.counting()))
  .equals(strB.chars().boxed().collect(Collectors.groupingBy(i -> i, Collectors.counting())));

Try it online.

怀疑此代码实际上具有 O(n) 的时间复杂度的人可以看到 live timing test 显示每个字母的恒定时间 - 即 O(n)（其中 n 是字母中的单词长度）。

Answer 2

你的算法的时间复杂度是 O(nlogn)。

检查两个字符串是否是字谜的运行时间应该是多少

What should be the runtime of checking if two strings are anagrams

java

runtime

permutation

anagram