242. 有效的字母异位词

1. 题目

给定两个字符串 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 仅包含小写字母

2. 思路

  • 由提示可知该题目仅包含小写字母，因此初始化map哈希数组用于存储每个字母出现的次数
  • 当两个字符串长度不一样时，则不可能是有效的字母异位词，因此可直接返回false
  • 遍历字符数组，对于s字符串出现的字符，则对哈希数组计数进行+1，对于t字符串出现的字符，则对哈希数组计数进行-1
  • 遍历完成后再依次确认map哈希数组的每个位置是否都为0，如果不为0则说明出现了差异化字母，此时直接返回false
  • 采取一正一负的抵消策略，有效的字母异位词应当在最后保证所有的计数都抵消为0

3. 代码

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
class Solution {
    public boolean isAnagram(String s, String t) {
        var map = new int[26];
        var sArr = s.toCharArray();
        var tArr = t.toCharArray();

        if (sArr.length != tArr.length) {
            return false;
        }

        for (var i = 0; i < sArr.length; ++i) {
            var sIndex = getIndex(sArr[i]);
            var tIndex = getIndex(tArr[i]);
            
            map[sIndex]++;
            map[tIndex]--;
        }

        for (var count : map) {
            if (count != 0) {
                return false;
            }
        }

        return true;
    }

    private int getIndex(char ch) {
        return ch - 'a';
    }
}

4. 复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

image-20230828221605997