两个单词如果包含相同的字母，次序不同，则称为字母易位词(anagram)。例如，“silent”和“listen”是字母易位词，而“apple”和“aplee”不是易位词。请定义函数检查两个单词是否是字母易位词。可以假设两个单词字母均为小写。要求算法复杂度尽量低。
我们可以看到用到两个for循环，一个会遍历n次，里层for循环我们假设最坏的情况是每次都走到最后一位（比如world和dlrow）,那么里面的次数是n,n-1,n-2…1，复杂程度为
n(n-1)/2=1/2*n^2+1/2*n=O(n^2) 2.是否可以先排序再一一比较就可以了，比较的时候最多是n次，那么我们的排序算法如果能降低复杂度的话，这也是一个好办法。 public static boolean compare2(String str1,String str2){ if (str1 == null && str2 == null) { return true; } if ((str1 == null && str2 != null) || (str1 != null && str2 == null) || str1.length() != str2.length()) { return false; } char[] str1ToChar = str1.toCharArray(); Arrays.sort(str1ToChar); char[] str2ToChar = str2.toCharArray(); Arrays.sort(str2ToChar); for(int i=0;i<str1.length();i++){ if(str1ToChar[i]!=str2ToChar[i]){ return false; } } return true; }我们知道java提供的排序算法复杂度是O(n*logn),两次排序加上比较：
2*O(n*logn)+n 3.我们希望能进一步减低算法复杂度，于是想到一个计数器，找到26大小的数组来记录每一个字母出现的次数，遍历第一个数组的时候，个数不断增加，遍历第二个数组的时候，不断减少，如果最后是0，就证明两个字符串中字符出现的次数都是一样的。 public static boolean compare(String str1,String str2){ if (str1 == null && str2 == null) { return true; } if ((str1 == null && str2 != null) || (str1 != null && str2 == null) || str1.length() != str2.length()) { return false; } int[] num = new int[26]; for(int i=0;i<str1.length();i++){ num[str1.charAt(i)-'a']++; } for(int i=0;i<str2.length();i++){ num[str2.charAt(i)-'a']--; } for(int i=0;i<num.length;i++){ if(num[i]!=0){ return false; } } return true; }我们可以看到这个算法中，遍历两次字符串2*n,又遍历一次m(m<=n). 所以算法的复杂度是：
2*n+m=O(n)总结：其实里面没有什么深奥的算法，只是一些小技巧，用空间来换取时间，一开始不比较，而是将字符串的异同表现在字符出现的个数上，这样子，问题就迎刃而解了。 此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~
技术之路不在一时，山高水长，纵使缓慢，驰而不息。
公众号：秦怀杂货店
