知一的指纹

字母异位词

版权声明: 本文为博主原创文章,发表自 知一的指纹。转载需向 我的邮箱 申请。

第一题:

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

示例 1:

输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:

输入: s = “rat”, t = “car”
输出: false

说明:
你可以假设字符串只包含小写字母。

解答第一个思路是使用 HashMap 进行字频统计再对比,第二个思路是字符串排序后进行比较。

第二题:

49. 字母异位词分组

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
说明:

所有输入均为小写字母。
不考虑答案输出的顺序。

练习输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.util.*;

public class Anagram {
public static void main(String[] args) {
System.out.println(isAnagram("anagram", "nagaram"));
System.out.println(isAnagram2("anagram", "nagaram"));
groupAnagrams(new String[]{"eat", "ate", "aaa"});
}

public static boolean isAnagram(String s, String t) {
if (null == s && null == t) {
return true;
} else if (null == s || null == t) {
return false;
} else if (s.length() != t.length()) {
return false;
}
Map<Character, Integer> left = new HashMap<>();
Map<Character, Integer> right = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
left.put(s.charAt(i), left.getOrDefault(s.charAt(i), 0) + 1);
}
for (int j = 0; j < t.length(); j++) {
right.put(t.charAt(j), right.getOrDefault(t.charAt(j), 0) + 1);
}
for (Map.Entry<Character, Integer> c : left.entrySet()) {
if (!c.getValue().equals(right.getOrDefault(c.getKey(), 0))) {
return false;
}
}

return true;
}

public static boolean isAnagram2(String s, String t) {
if (null == s && null == t) {
return true;
} else if (null == s || null == t) {
return false;
} else if (s.length() != t.length()) {
return false;
}
char[] left = s.toCharArray();
char[] right = t.toCharArray();
Arrays.sort(left);
Arrays.sort(right);
for (int i = 0; i < left.length; i++) {
if (left[i] != right[i]) {
return false;
}
}
return true;
}

public static List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> res = new HashMap<>();
for (String sr : strs) {
char[] chars = sr.toCharArray();
Arrays.sort(chars);
String sortedSr = new String(chars);
if (!res.containsKey(sortedSr)) {
res.put(sortedSr, new ArrayList<>());
}
List<String> mapVal = res.get(sortedSr);
mapVal.add(sr);
}
List<List<String>> rep = new ArrayList<>();
for (Map.Entry<String, List<String>> entry : res.entrySet()) {
rep.add(entry.getValue());
}
return rep;
}
}

如果此文章能给您带来小小的提升,不妨小额赞赏我一下,以鼓励我写出更好的文章!
Noogel's WeChat Pay

微信打赏

Noogel's Alipay

支付宝打赏