我正在处理一个排列/字谜问题,并希望输入最有效的检查方法。现在,我正在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)的循环。
因此,在这两种方法中,仅具有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;
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句