java – anagram检查的最佳解决方案?
发布时间:2020-12-15 04:34:57 所属栏目:Java 来源:网络整理
导读:我正在经历一个排列/字谜问题,并希望输入最有效的检查方法. 现在,我正在 Java土地上这样做,因此有一个包括排序在内的一切图书馆. 检查两个字符串是否是彼此的字谜的第一种方法是检查长度,以某种方式对它们进行排序,然后比较所述字符串的每个索引.代码如下:
我正在经历一个排列/字谜问题,并希望输入最有效的检查方法.
现在,我正在 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 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; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |