我正在处理一个排列/字谜问题,希望就最有效的检查方法提供意见。 现在,我在 Java 领域做这件事,因此有一个库可以处理一切,包括排序。 检查两个字符串是否是彼此的变位词的第一种方法是检查长度,以某种方式对它们进行排序,然后比较所述字符串的每个索引。代码如下:
private boolean validAnagram(String str, String pair) {
if(str.length() != pair.length()){
return false;
}
char[] strArr = str.toCharArray();
char[] pairArr = pair.toCharArray();
Arrays.sort(strArr);
str = new String(strArr);
Arrays.sort(pairArr);
pair = new String(pairArr);
for(int i = 0; i<str.length(); i++){
if(str.charAt(i) != pair.charAt(i)){
return false;
}
}
return true;
}
或者,我认为基于 ascii 值进行检查会更容易,并且避免检查每个可能的字符。代码如下:
private boolean validAnagram(String str, String pair) {
if(str.length() != pair.length()){
return false;
}
char[] strArr = str.toCharArray();
char[] pairArr = pair.toCharArray();
int strValue = 0;
int pairValue = 0;
for(int i =0; i < strArr.length; i++){
strValue+= (int) strArr[i];
pairValue+= (int) pairArr[i];
}
if(strValue != pairValue){
return false;
}
return true;
}
那么,哪个是更好的解决方案?我不太了解 Arrays 给我的那种类型,但是当我环顾旧的互联网时,这是更常见的答案。让我想知道我是否遗漏了什么。
最佳答案
有几种方法可以检查两个字符串是否是变位词。 你的问题是,哪一个是更好的解决方案。 您的第一个解决方案具有排序逻辑。 排序的最坏情况复杂度为 (nlogn) 。 您的第二个逻辑仅使用一个具有复杂性的循环 在) 。
所以在这两个中,你的第二个解决方案只有 O(n) 复杂性将是比第一个更好的解决方案。
一个可能的解决方案:
private boolean checkAnagram(String stringOne, String stringTwo){
char[] first = stringOne.toLowerCase().toCharArray();
char[] second = stringTwo.toLowerCase().toCharArray();
//如果字符串长度不同
if (first.length != second.length)
返回假;
int[] counts = new int[26];
对于 (int i = 0; i < first.length; i++){
计数[第一个[i]-97]++;
计数[秒[i]-97]--;
}
对于 (int i = 0; i<26; i++)
如果(计数[i]!= 0)
返回假;
返回真;
}
关于java - 字谜检查的最佳解决方案?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38229648/