leetcode 242. Valid Anagram
- Valid Anagram:题目链接
方法1：hash table
利用一个哈希表来记录字符串中对应字符出现的频率
int[26] for Letters 'a' - 'z' or 'A' - 'Z'
int[128] for ASCII
int[256] for Extended ASCII
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
| public class Solution1 {
// 时间复杂度O(N)
public boolean isAnagram(String s, String t) {
int[] hash = new int[256]; //来存放该字符出现的频率
// 统计t中字符出现的频率 hash['a'] = hash[97]
for (char ch : t.toCharArray()) {
hash[ch]++;
}
// 如果两者长度不相等 说明肯定不是
if (s.length() != t.length()) {
return false;
}
// 遍历s
for (int i = 0; i < s.length(); ++i) {
if (hash[s.charAt(i)] > 0) { // s.charAt(i)当前出现频率 > 0 说明s中与t都有该字符
hash[s.charAt(i)]--; // 对应频率减1
} else {
return false;
}
}
return true;
}
public static void main(String[] args) {
String s = "anagram";
String t = "nagaram";
System.out.println(new Solution1().isAnagram(s, t));
}
}
|
方法2：
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
| import java.util.HashMap;
import java.util.Map;
public class Solution2 {
public boolean isAnagram(String s, String t) {
Map<Character, Integer> map = new HashMap<>();
for (char ch : t.toCharArray()) {
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
if (s.length() != t.length()) {
return false;
}
for (int i = 0; i < s.length(); ++i) {
if (map.containsKey(s.charAt(i)) && map.get(s.charAt(i)) > 0) {
map.put(s.charAt(i), map.get(s.charAt(i)) - 1);
} else {
return false;
}
}
return true;
}
public static void main(String[] args) {
String s = "anagram";
String t = "nagaram";
System.out.println(new Solution1().isAnagram(s, t));
}
}
|
pS: 源代码链接
