本文主要是介绍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中貌似有类似的,以后碰到字符串的题目,很多都能用字符串数组来求解,方便快捷,同时时间复杂度还低,因此,这种思路是非常重要的。
这篇关于Anagram 字母易位词的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!