【LeetCode】242. 有效的字母异位词 - hashmap

242. 有效的字母异位词

2023-9-4 09:24:54

中规中矩的做法：先把第一个字符串的字符和对应出现的次数放进hashmap里面。第二个字符串则出现一个字符就减去一次，如果减去的时候 出现了负数，则返回false。如果第二个字符串遍历完了，都没有返回false的情况，那么则证明二者是字母异位词。

class Solution {

    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()){
            return false;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (map.containsKey(c)){
                Integer integer = map.get(c);
                map.put(c, ++integer);
            }else {
                map.put(c, 1);
            }
        }

        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (map.containsKey(c)){
                Integer integer = map.get(c);
                if (integer-- < 1){
                    return false;
                }
                map.put(c, integer);
            }else {
                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
24
25
26
27
28
29
30
31
32
33

中规中矩的做法会发现复杂度挺多的。优化：

由于题目中 s 和 t 仅包含小写字母，并且我们可以一遍遍历完 第一个字符串（每出现一次，字母出现的次数+1）和第二个字符串（每出现一次，字母出现的次数 -1），并把遍历的结果放入数组添加链接描述中。

再遍历数组，如果发现有一个元素对应的值是不等于0的，则证明二者不是字母异位词；反之，则是字母异位词。

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length())
            return false;
        int[] alpha = new int[26];
        for (int i = 0; i < s.length(); i++) {
            alpha[s.charAt(i) - 'a']++;
            alpha[t.charAt(i) - 'a']--;
        }
        for (int i = 0; i < 26; i++)
            if (alpha[i] != 0)
                return false;
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15