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

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) - 通常应尽可能避免。

您可以通过对每个字符串进行一次传递来收集字符频率，然后使用 Map#equals 进行比较，从而将时间复杂度降低到 O(n)。

只需一行即可完成此操作:

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 是字母中的单词长度)。