242. 有效的字母异位词

给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。

注意：若 *s* 和 *t* 中每个字符出现的次数都相同，则称 *s* 和 *t* 互为字母异位词。

示例 1:

1
2
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

1
2
输入: s = "rat", t = "car"
输出: false

提示:

  • 1 <= s.length, t.length <= 5 * 104
  • s 和 t 仅包含小写字母

题解：

方法一：

哈希表

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
public static boolean isAnagram(String s, String t) {
    //如果两字符串长度不相等，则肯定不符合要求
    if (s.length() != t.length()) {
        return false;
    }

    HashMap<Character, Integer> map = new HashMap<>();

    //将第一个字符串s存入哈希表，字符为键，出现的次数为值
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        map.put(c, map.getOrDefault(c, 0) + 1);

    }
    //判断第二个字符串中的逐个字符，如果存在，则更新次数，不存在直接返回false
    for (int i = 0; i < t.length(); i++) {
        char c = t.charAt(i);
        if (map.keySet().contains(c)) {
            int count = map.get(c);
            if (count > 0) {
                map.put(c, --count);
            } else {
                return false;
            }
        } else {
            return false;
        }
    }
    return true;
}
  • 时间复杂度：O(n)，n是字符串s的长度
  • 空间复杂度：O(|S|)，S为字符集的大小，此处为26。

方法2：

排序，字母异位词代表字符以及字符的个数要一致，则等价于排序后两字符串相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static boolean isAnagram(String s, String t) {
    if (s.length() != t.length()){
        return false;
    }
    char[] chars = s.toCharArray();
    char[] chart = t.toCharArray();

    Arrays.sort(chars);
    Arrays.sort(chart);

    return Arrays.equals(chars,chart);

}
  • 时间复杂度:O(logN)，排序所用到的时间复杂度
  • 空间复杂度：O(logN)，排序所用到的空间复杂度