problem
Given two strings s and t , write a function to determine if t is an anagram of s.
Example 1:
1
2
| Input: s = "anagram", t = "nagaram"
Output: true
|
Example 2:
1
2
| Input: s = "rat", t = "car"
Output: false
|
Note:
You may assume the string contains only lowercase alphabets.
Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?
approach 1
算法
sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| /*
* @lc app=leetcode id=242 lang=java
*
* [242] Valid Anagram
*/
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] s1 = s.toCharArray();
char[] t1 = t.toCharArray();
Arrays.sort(s1);
Arrays.sort(t1);
return Arrays.equals(s1, t1);
}
}
|
复杂度
- time:O(nlogn) 快排
- space:O()
approach 2
算法
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
| /*
* @lc app=leetcode id=242 lang=java
*
* [242] Valid Anagram
*/
class Solution {
public boolean isAnagram(String s, String t) {
Map<Character, Integer> m1 = countCharacter(s);
Map<Character, Integer> m2 = countCharacter(t);
return m1.equals(m2);
}
private Map<Character, Integer> countCharacter(String str) {
Map<Character, Integer> m = new HashMap<>();
for (Character c : str.toCharArray()) {
Integer cnt = m.get(c);
if (cnt == null) {
m.put(c, 1);
} else {
m.put(c, ++cnt);
}
}
return m;
}
}
|
复杂度
approach 3
算法
相当自建hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] counter = new int[26];
for (int i = 0; i < s.length(); i++) {
counter[s.charAt(i) - 'a']++;
counter[t.charAt(i) - 'a']--;
}
for (int count : counter) {
if (count != 0) {
return false;
}
}
return true;
}
|
复杂度