最小复杂度的Anagram算法
我最近被要求设计一种算法来检查两个字符串是否是彼此的字谜。我的目标是最小化空间和时间复杂度，所以我提出了这个算法：
创建一个包含26个元素的数组，每个元素初始化为零。
遍历第一个字符串，对于每个字符，递增与该字符对应的数组元素。
遍历第二个字符串，对于每个字符，递减与该字符对应的数组元素。
扫描阵列。如果所有元素都是0，则两个字符串是字谜。
然而，该算法的时间复杂度为O（n），我无法提出复杂度较低的算法。有人知道吗？
没有找到相关结果
已邀请:
5 个回复
辅奈
咖哀烈
布埃郝卞簿
死簇
public class Method1 { public static void main(String[] args) { String a = "protijayi"; String b = "jayiproti"; System.out.println(isAnagram(a, b ));// output => true } private static boolean isAnagram(String a, String b) { Map<Character ,Integer> map = new HashMap<>(); for( char c : a.toCharArray()) { map.put(c, map.getOrDefault(c, 0 ) + 1 ); } for(char c : b.toCharArray()) { int count = map.getOrDefault(c, 0); if(count == 0 ) {return false ; } else {map.put(c, count - 1 ) ; } } return true; } }public class Method2 { public static void main(String[] args) { String a = "protijayi"; String b = "jayiproti"; System.out.println(isAnagram(a, b));// output=> true } private static boolean isAnagram(String a, String b) { int[] alphabet = new int[26]; for(int i = 0 ; i < a.length() ;i++) { alphabet[a.charAt(i) - 'a']++ ; } for (int i = 0; i < b.length(); i++) { alphabet[b.charAt(i) - 'a']-- ; } for( int w : alphabet ) { if(w != 0 ) {return false;} } return true; } }public class Method3 { public static void main(String[] args) { String a = "protijayi"; String b = "jayiproti"; System.out.println(isAnagram(a, b ));// output => true } private static boolean isAnagram(String a, String b) { char[] ca = a.toCharArray() ; char[] cb = b.toCharArray(); Arrays.sort( ca ); Arrays.sort( cb ); return Arrays.equals(ca , cb ); } }public class Method4 { public static void main(String[] args) { String a = "protijayi"; String b = "jayiproti"; //String c = "gini"; System.out.println(isAnagram(a, b ));// output => true } private static boolean isAnagram(String a, String b) { Map<Integer, Integer> map = new HashMap<>(); a.codePoints().forEach(code -> map.put(code, map.getOrDefault(code, 0) + 1)); b.codePoints().forEach(code -> map.put(code, map.getOrDefault(code, 0) - 1)); //System.out.println(map.values()); for(int count : map.values()) { if (count<0) return false; } return true; } }恋卡
int anagram (char a[], char b[]) { char chars[26]; int ana = 0; int i =0; for (i=0; i<26;i++) chars[i] = 0; if (strlen(a) != strlen(b)) return -1; i = 0; while ((a[i] != ' ') || (b[i] != ' ')) { chars[a[i] - 'a']++; chars[b[i] - 'a']--; i++; } for (i=0; i<26;i++) ana += chars[i]; return ana; } void main() { char *a = "chimmy "; char *b = "yimmch "; printf ("Anagram result is %d.n", anagram(a,b)); }