十大排序从入门到入赘 - 力扣（LeetCode）
题目分析：
实际上求每个单词出现的次数是否是相同的
方法一：
利用暴力求解出，对字符串进行排序，并比较是否相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public boolean isAnagram(String s, String t) {
if(s.length()!=t.length()){
return false;
}
char[] str1= s.toCharArray();
char[] str2= t.toCharArray();
Arrays.sort(str1);
Arrays.sort(str2);
return Arrays.equals(str1,str2);
}
}
|
时间复杂度：O(n \log n)O(nlogn)，其中 nn 为 ss 的长度。排序的时间复杂度为 O(n\log n)O(nlogn)，比较两个字符串是否相等时间复杂度为 O(n)O(n)，因此总体时间复杂度为 O(n \log n+n)=O(n\log n)O(nlogn+n)=O(nlogn)。
空间复杂度：O(\log n)O(logn)。排序需要 O(\log n)O(logn) 的空间复杂度。注意，在某些语言（比如 Java & JavaScript）中字符串是不可变的，因此我们需要额外的 O(n)O(n) 的空间来拷贝字符串。但是我们忽略这一复杂度分析，因为：
这依赖于语言的细节；
这取决于函数的设计方式，例如，可以将函数参数类型更改为 char[]。
方法二：
将元素放入Map中，判断最后是否是空值。
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
| public boolean isAnagram(String s, String t) {
if(s.length()!=t.length()){
return false;
}
char[] str1= s.toCharArray();
char[] str2= t.toCharArray();
HashMap<Character,Integer> map = new HashMap<>();
for(int i=0;i<str1.length;i++){
Integer tempValue = map.get(str1[i]);
if (tempValue!=null&&tempValue>=1){
map.put(str1[i],tempValue+1);
}else{
map.put(str1[i],1);
}
}
for(int i=0;i<str2.length;i++){
Integer tempValue = map.get(str2[i]);
if (tempValue!=null&&tempValue>0){
tempValue =tempValue-1;
if (tempValue>0){
map.put(str2[i],tempValue);
}else{
map.remove(str2[i]);
}
}
}
return map.isEmpty();
}
}
|
方法三：
使用hash表的底层实现的数组，我们自己写hash函数
key是26个英文字母，value是保存出现的次数， hash函数就是x-‘a’,100%不存在hash碰撞
- 从单词首位开始遍历数组
- 遍历的同时，对于每一个s中的字母，map中的value +1， t中的字母，map中的value -1
3.遍历结束后，我们看是否全部的value都为0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public boolean isAnagram(String s, String t) {
int len = s.length();
if(len != t.length())
return false;
int[] arr = new int[26];
for(int i = 0; i < len; i++) {
arr[s.charAt(i) - 'a']++;
arr[t.charAt(i) - 'a']--;
}
for(int i = 0; i < 26; i++){
if(arr[i] != 0)
return false;
}
return true;
}
|
方法一
由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
char[] array = str.toCharArray();
Arrays.sort(array);
String key = new String(array);
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
|
复杂度分析
