字谜检查的最佳解决方案？

Question

我\xe2\x80\x99m 正在经历一个排列/字谜问题，并希望输入最有效的检查方法。\n现在，我\xe2\x80\x99m 在 Java 领域执行此操作，因此有一个可以处理所有内容的库包括排序。\n检查两个字符串是否互为字谜的第一种方法是检查长度，以某种方式对它们进行排序，然后比较所述字符串的每个索引。代码如下：

\n\n

private boolean validAnagram(String str, String pair) {\nif(str.length() != pair.length()){\n    return false;\n}\n\nchar[] strArr = str.toCharArray();\nchar[] pairArr = pair.toCharArray();\n\n\nArrays.sort(strArr);\nstr = new String(strArr);\n\nArrays.sort(pairArr);\npair = new String(pairArr);\n\nfor(int i = 0; i<str.length(); i++){\n    if(str.charAt(i) != pair.charAt(i)){\n        return false;\n    }\n}\nreturn true;\n}\n

\n\n

或者，我认为根据 ascii 值进行检查会更容易，并避免检查每个可能的字符。代码如下：

\n\n

private boolean validAnagram(String str, String pair) {\nif(str.length() != pair.length()){\n    return false;\n}\n\nchar[] strArr = str.toCharArray();\nchar[] pairArr = pair.toCharArray();\n\n\n\nint strValue = 0;\nint pairValue = 0;\n\nfor(int i =0; i < strArr.length; i++){\n    strValue+= (int) strArr[i];\n    pairValue+= (int) pairArr[i];\n}\n\nif(strValue != pairValue){\n    return false;\n}\nreturn true;\n}\n

\n\n

那么，哪个是更好的解决方案？我不太了解数组给我的排序，但是当我浏览旧互联网时，\xe2\x80\x99 是更常见的答案。让我想知道我\xe2\x80\x99m 是否遗漏了一些东西。

\n

Answer 1

有多种方法可以检查两个字符串是否是字谜词。你的问题是，哪一种是更好的解决方案。您的第一个解决方案具有排序逻辑。排序的最坏情况复杂度为 (nlogn) 。您的第二个逻辑仅使用一个复杂度为 O(n) 的循环。

因此，在这两个解决方案中，只有 O(n) 复杂度的第二个解决方案将比第一个解决方案更好。

一种可能的解决方案：

private boolean checkAnagram(String stringOne , String stringTwo){
        char[] first = stringOne.toLowerCase().toCharArray(); 
        char[] second = stringTwo.toLowerCase().toCharArray();
        // if length of strings is not same 
        if (first.length != second.length)
            return false;
        int[] counts = new int[26]; 
        for (int i = 0; i < first.length; i++){
            counts[first[i]-97]++;  
            counts[second[i]-97]--;   
        }
        for (int i = 0; i<26; i++)
            if (counts[i] != 0)
                return false;
        return true;
    }