（编程题）字母易位词

字母易位词"/>

（编程题）字母易位词

题目

两个单词如果包含相同的字母，次序不同，则称为字母易位词(anagram)。例如，“silent”和“listen”是字母易位词，而“apple”和“aplee”不是易位词。请定义函数检查两个单词是否是字母易位词。可以假设两个单词字母均为小写。要求算法复杂度尽量低。

思路

• 1.暴力破解：判断str1中的每一个字母是否出现在str2中，同时我们需要一个大小与字符串位数一致的数组来记录str2中已经被标记的位。

  public static boolean compare(String str1, String str2) {int i,j;if (str1 == null && str2 == null) {return true;}if ((str1 == null && str2 != null)|| (str1 != null && str2 == null)|| str1.length() != str2.length()) {return false;}// boolean 默认是falseboolean[] flags = new boolean[str2.length()];for (i = 0; i < str1.length(); i++) {char temp = str1.charAt(i);for (j = 0; j < str2.length(); j++) {if (str2.charAt(j) == temp && !flags[j]) {flags[j]=true;break;}}if(j>=str2.length()){return false;}}return true;}

我们可以看到用到两个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)

总结：其实里面没有什么深奥的算法，只是一些小技巧，用空间来换取时间，一开始不比较，而是将字符串的异同表现在字符出现的个数上，这样子，问题就迎刃而解了。
此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~

技术之路不在一时，山高水长，纵使缓慢，驰而不息。

公众号：秦怀杂货店