Anagram 字母易位词

字母易位词"/>

Anagram 字母易位词

两个单词如果包含有相同的字母，只是次序不同，则称这两个词为字母易位词，例如："silent"和"listen".而"apple"和"aplee"就不是字母易位词。请用最小的算法复杂度来实现监测两个单词是否是字母易位词。

看到这个题，需要用最小的时间复杂度来判断，那么如果用比较一般的方法，比如用hashMap来实现，算法的时间复杂度就会比较高。那么就需要另辟蹊径，找一个简单的方法。关于字符串的题目，很多可以采用构造一个数组，其中，数组的长度表示26个字母，那么数组里的数字表示该字母在字符串中出现的次数。那针对这题，就可以用空间换时间，用O(n)的时间复杂度来完成，首先用一个字符串来扫描一遍整个数组，然后用另一个字符串去扫描该数组，如果出现数组中的数字小于该数组中的数字，那么就说明这两个字符串不是字母易位词。

    public static boolean isAnagram(String s1,String s2){int[] num = new int[26];if(s1.length() != s2.length())return false;for(int i = 0; i < s1.length(); i++){num[s1.charAt(i) - 'a']++;}for(int j = 0; j < s2.length(); j++){if(--num[s2.charAt(j) - 'a'] < 0)return false;}return true;}

此题在leetcode中貌似有类似的，以后碰到字符串的题目，很多都能用字符串数组来求解，方便快捷，同时时间复杂度还低，因此，这种思路是非常重要的。