本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
242. 有效的字母异位词
本题来自LeetCode：242. 有效的字母异位词[1]
题目描述
给定两个字符串 s 和 t ，编写一个函数来判断
t是否是
s的字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
解法一
题目分析
字母异位词：两个字符串长度相等，每个字符出现的次数相等。
根据定义，我们可以统计两个字符串的每个字符出现的个数，然后比较每个字符出现的个数是否相等。
采用长度为
26的
数组记录字母出现的个数。
题目解答
class Solution {
public boolean isAnagram(String s, String t) {
if(s == t) {
return true;
}
if(s == null || t == null || s.length() != t.length()) {
return false;
}
int[] countS = getCount(s);
int[] countT = getCount(t);
// 比较两个字符串每个字母出现的次数是否相等
for(int i = 0; i 26; i ++) {
if(countS[i] != countT[i]) {
return false;
}
}
return true;
}
// 统计每个字母出现的次数
public int[] getCount(String s) {
int[] count = new int[26];
for(int i = 0; i s.length(); i ++) {
count[s.charAt(i) - 'a'] += 1;
}
return count;
}
}
复杂度分析：
时间复杂度：
O(n)，
n为字符串长度
空间复杂度：
O(1)，字母个数最多为26个，本题额外空间为数组。
解法二
题目分析
本解法采用
哈希表记录字符出现的个数，也适用包含
unicode字符的场景。
题目解答
class Solution {
public boolean isAnagram(String s, String t) {
if(s == t) {
return true;
}
if(s == null || t == null || s.length() != t.length()) {
return false;
}
MapCharacter, Integer map = new HashMap();
for(int i = 0; i s.length(); i ++) {
// 统计字符串s每个字符出现的次数，出现一次 +1
Character c = s.charAt(i);
Integer count = map.getOrDefault(c, 0);
map.put(c, ++ count);
// 统计字符串t每个字符出现的次数，出现一次 -1
c = t.charAt(i);
count = map.getOrDefault(c, 0);
map.put(c, --count);
}
// 若s和t互为字母异位词，那么所有字符的个数是相等的，故map中的字符都抵消掉了
for(Integer count : map.values()) {
if(count != 0) {
return false;
}
}
return true;
}
}
复杂度分析：
时间复杂度：
O(n)，
n为字符串长度
空间复杂度：
O(1)，字母个数最多为26个，本题额外空间为哈希表。
解法三
题目分析
也可以将字符串
s每个字符出现个数的统计数据，转换为一个新的字符串
s'，为原字符串各个字符的排序后的字符串。比如原字符串
baadb，经过排序后生成新的字符串
aabbd。
若
s和
t为字母异位词，那么
s' = t'。
采用
哈希表记录字符出现的个数，本解法也适用包含
unicode字符的场景。
题目解答
class Solution {
public boolean isAnagram(String s, String t) {
if(s == t) {
return true;
}
if(s == null || t == null || s.length() != t.length()) {
return false;
}
// 比较转换后的字符串是否相等
return convert(s).equals(convert(t));
}
// TreeMap用于排序
public MapCharacter, Integer map = new TreeMap();
// 转换成按字符顺序排列的字符串
public String convert(String s) {
map.clear();
// 统计每个字符出现的次数
for(int i = 0; i s.length(); i ++) {
Character c = s.charAt(i);
Integer count = map.getOrDefault(c, 0);
map.put(c, ++ count);
}
StringBuilder sb = new StringBuilder();
// 按字符顺序转换为字符串
for(Map.EntryCharacter, Integer entry : map.entrySet()) {
Character c = entry.getKey();
Integer count = entry.getValue();
while(count != 0) {
sb.append(c);
count --;
}
}
return sb.toString();
}
}
复杂度分析：
时间复杂度：
O(n)，
n为字符串长度
空间复杂度：
O(1)，字母个数最多为26个，本题额外空间为哈希表。
49. 字母异位词分组
本题来自LeetCode：49. 字母异位词分组[2]
题目描述
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
解法一
题目分析
全是小写字母，由
242. 有效的字母异位词的
解法一，可以得到本题的解法。我们可以得到每个字符串的每个字符的统计数据，通过
个数+.的形式连接成
c'，则相同的字母异位词组合，用于同一个
c'。
题目解答
class Solution {
public ListListString groupAnagrams(String[] strs) {
MapString, ListString result = new HashMap();
for(int i = 0; i strs.length; i ++) {
// 转换为按字符顺序排列的字符串
String s = getCountString(strs[i]);
// 找到字母异位词
ListString list = result.getOrDefault(s, new ArrayList());
list.add(strs[i]);
result.put(s, list);
}
return new ArrayList(result.values());
}
// 统计每个字母出现的次数,返回同统计数据，按照 个数 + "."的形式连接起来
public String getCountString(String s) {
int[] count = new int[26];
for(int i = 0; i s.length(); i ++) {
count[s.charAt(i) - 'a'] += 1;
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i 26; i ++) {
sb.append(count[i]).append(".");
}
return sb.toString();
}
}
复杂度分析：
时间复杂度：
O(totalLength)，
totalLength为字符串的总长度
空间复杂度：
O(n)，
n为数组长度，每个字符串生成一个
int[]和
StringBuilder
解法二
题目分析
由
242. 有效的字母异位词的
解法三，可以得到本题的解法。适用包含
unicode字符的场景。当然本题还有很多优化空间，比如和
242 题的解法一一样，由于全是小写字母，直接用长度为26的数组替代哈希表。比较是否为
题目解答
class Solution {
public ListListString groupAnagrams(String[] strs) {
MapString, ListString result = new HashMap();
for(int i = 0; i strs.length; i ++) {
// 转换为按字符顺序排列的字符串
String s = convert(strs[i]);
// 找到字母异位词
ListString list = result.getOrDefault(s, new ArrayList());
list.add(strs[i]);
result.put(s, list);
}
return new ArrayList(result.values());
}
// TreeMap用于排序
public MapCharacter, Integer map = new TreeMap();
// 转换成按字符顺序排列的字符串
public String convert(String s) {
// 初始化
map.clear();
// 统计每个字符出现的次数
for(int i = 0; i s.length(); i ++) {
Character c = s.charAt(i);
Integer count = map.getOrDefault(c, 0);
map.put(c, ++ count);
}
StringBuilder sb = new StringBuilder();
// 按字符顺序转换为字符串
for(Map.EntryCharacter, Integer entry : map.entrySet()) {
Integer count = entry.getValue();
while(count != 0) {
sb.append(entry.getKey());
count --;
}
}
return sb.toString();
}
}
复杂度分析：
时间复杂度：
O(totalLength)，
totalLength为字符串的总长度
空间复杂度：
O(n)，
n为数组长度，每个字符串生成一个
StringBuilder
参考资料
原文始发于微信公众号（xiaogan的技术博客）：
