在看散列表相关LeetCode题之前，先放个传送门【数据结构】散列表，从特性分析到散列冲突再到应用总结…
242. 有效的字母异位词¹
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
说明: 你可以假设字符串只包含小写字母。
异位词：组成相同，顺序不同
解法一：双重循环
思路：很简单，就是判断两个字符串的组成是否完全相同。落实在代码上就是嵌套for循环：外层遍历s，内层遍历t寻找与s当前字符相同的字符，若存在就将t中相同字符置为空（注：这里用 replaceFirst）复杂度
Time：O(m*n)，m是s的长度，n是t的长度Space：O(1)
public boolean isAnagram(String s
, String t
) {
if (s
.length() != t
.length()) return false;
boolean res
= true;
for (int i
= 0; i
< s
.length(); i
++) {
for (int j
= 0; j
< t
.length(); j
++) {
res
= false;
if (s
.charAt(i
) == t
.charAt(j
)) {
res
= true;
t
= t
.replaceFirst(String
.valueOf(t
.charAt(j
)),"");
break;
}
}
if (!res
) break;
}
return res
;
}
解法二：散列表
思路：记录每个字符的出现次数，这其实是一种K-V思想，所以可以用到散列表
因为总共才26个字母，所以一个数组（alph[26]）就够了。其中，key是数组索引，v是字符出现次数的计数当s中有某个字符时 alph[s.charAt(i) - ‘a’]++，而当t中有某个字符时 alph[t.charAt(i) - ‘a’]–，最后看aplh中是否所有字符的计数为0 复杂度
Time：O(n)Space：O(1)，因为只有26个字母，所以数组的大小与数据规模无关
public boolean isAnagram(String s
, String t
) {
int[] alph
= new int[26];
for(int i
= 0; i
< s
.length(); i
++) alph
[s
.charAt(i
) - 'a']++;
for(int i
= 0; i
< t
.length(); i
++) alph
[t
.charAt(i
) - 'a']--;
for(int i
: alph
) if(i
!= 0) return false;
return true;
}
这里再强调一下，散列表一般用与需要K-V思想的场景。落实在代码上分为两种情况：当散列表只需要保存value时，用数组就行；而当要同时保存key和value时，一般用HashMap。
49. 字母异位词分组²
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
所有输入均为小写字母。不考虑答案输出的顺序。
解法：散列表（HashMap）
思路：由于所有 list 的字母组成相同，所以本题其实也包含了 K-V 的思想，可以用到散列表
这里可以使用HashMap，key是String表示公有字符，value是List表示key组成的不同字符串若当前字符串与key相同组成，则取出key的List然后add若不存在，则将这个key放入map，并新建一个List 细节
key：必须要将字符串，先化为数组进行排序（toCharrArray)，然后再化为字符串作为key(String.valueOf)在返回List<List>时，new ArrayList<List>(map.values())
public List
<List
<String>> groupAnagrams(String
[] strs
) {
Map
<String
,List
<String>> map
= new HashMap<>();
for (int i
= 0; i
< strs
.length
; i
++) {
char[] c
= strs
[i
].toCharArray();
Arrays
.sort(c
);
String key
= String
.valueOf(c
);
if (map
.containsKey(key
)) {
map
.get(key
).add(strs
[i
]);
}else {
List
<String> l
= new ArrayList<>();
l
.add(strs
[i
]);
map
.put(key
,l
);
}
}
return new ArrayList<List
<String>>(map
.values());
}
代码优化，优化了if-else，代码更简洁可读：
public List
<List
<String>> groupAnagrams(String
[] strs
) {
Map
<String
,List
<String>> map
= new HashMap<>();
for (int i
= 0; i
< strs
.length
; i
++) {
char[] c
= strs
[i
].toCharArray();
Arrays
.sort(c
);
String key
= String
.valueOf(c
);
if (!map
.containsKey(key
))
map
.put(key
, new ArrayList<String>());
map
.get(key
).add(strs
[i
]);
}
return new ArrayList<List
<String>>(map
.values());
}
