力扣242.有效的字母异位词(Java语言，排序法、散列表法)

字母异位词(Java语言，排序法、散列表法)"/>

力扣242.有效的字母异位词(Java语言，排序法、散列表法)

题目描述：

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

解题思路：

思路1：排序法

根据题目意思，判断两个字符串是否为有效字母异位词就是*判断它们的字母出现次数是否相同！*由此我们可以想到我们一个个比较不就行了吗，在此基础上我们可以又联想到两个方向：

1.较常见的映射关系用散列表解决(思路2)
2.我们暴力一些，先将两个字符串排好序，再将比较两个字符串，相同则返回true否则false

思路2：散列表法

我们以两个字符串的字符作为键，出现的次数作为值，进行统计比较（此处我不重点分析解题的大体逻辑，而是重点由此题分享用java语言散列表解题时的常用技巧，对于其他语言大家可以根据自己所学语言的特性实现，思路都是相同的！！！）
对于在使用散列表解题时一般都有两种方法：

1.手动利用数组实现散列表（具体根据题目的需求将数组的索引和对应索引存储的值作为键和值）
2.利用语言提供的接口自己根据定义合理选定键与值(Java中常用HashMap)

对于本题目:

1.若我们手动维护一个散列表（本题目所有的字母是小写），我们常用的技巧是获取每个字符的ASCLL码值并减去小写字母a的ASCLL码值作为数组的索引即作为散列表的键（用此技巧的目的就是更有效的利用数组空间即我们不必开辟太大的空间以至于造成浪费），然后先遍历字符串s，再让每个对应位置的数值加一；再遍历字符串t，让每个对应位置的数值减去1，最后遍历判断数组，若有位置的数值小于0则返回false否则返回true
2.若我们使用HashMap接口（大体思路不再赘述，和1思想一样，具体分享技巧），我们常用一个getOrDefault(key,defaultValue)方法（当map中存在键时值为自己设定的默认值defaultValue）,在此基础上，若我们常进行此操作（用于统计和最后的比较）：

自定义的Hashmap.put(key,自定义的Hashmap.getOrDefault(key,defauliValue) +或者- int值)

代码：

思路1：

class Solution {//Sort//Time Complexity: O(NlogN)//Space Complexity: O(N)public boolean isAnagram(String s, String t) {if (s.length() != t.length()) {return false;}char[] arrS = s.toCharArray();char[] arrT = t.toCharArray();Arrays.sort(arrs);Arrays.sort(arrT);return Arrays.equals(arrS,arrT);}
}

思路2：

（1）：

class Solution {//HashTable//Time Complexity: O(N)//Space Complexity: O(M)(此处M为26)public boolean isAnagram(String s, String t) {if (s.length() != t.length()) {return false;}int[] table = new int[26];//先遍历s，对应索引位置++for (int i = 0; i < s.length(); i++) {table[s.charAt(i) - 'a']++;}//再遍历t,对应索引位置--for (int j = 0; j < t,length(); j++) {table[t.charAt(j) - 'a']--;}//遍历tablefor (int k = 0; k < table.length; k++) {if (table[k] < 0) {return false;}}return true;}
}

(2):

class Solution {//HasMap//Time Complexity: O(NlogN)//Space Complexity: O(M)public boolean isAnagram(String s, String t) {if (s.length() != t.length()) {return false;}HashMap<Character, Integer> map = new HashMap<>();for (int i = 0; i < s.length(); i++) {char charS = s.charAt(i);map.put(charS, map.getOrDefault(charS,0) + 1);}for (int j = 0; j < t.length(); ++j) {char charT = t.charAt(j);map.put(charT,map.getOrDefault(charT,0) - 1);//判断if (map.get(charT) < 0) {return false;}}return true;}
}