242. Valid Anagram

[242. Valid Anagram](https://leetcode.com/problems/valid-anagram/)

判断字符是否是重排字符

Solution 1 str转array-排序array后比较

思路：string转char array，对char array进行排序；再比较两个数组是否相等即可。

Runtime: 2 ms, faster than 94.75% of Java online submissions for Valid Anagram.

Memory Usage: 39.4 MB, less than 40.34% of Java online submissions for Valid Anagram.

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean isAnagram(String s, String t) {
        char[] chars1 = s.toCharArray();
        char[] chars2 = t.toCharArray();
        Arrays.sort(chars1);
        Arrays.sort(chars2);
        return Arrays.equals(chars1, chars2);
    }
}

Solution 2 str转array-map统计字符出现次数

思路：string转char array，对char array中出现的字符及其次数进行统计，再比较。

Runtime: 11 ms, faster than 23.84% of Java online submissions for Valid Anagram.

Memory Usage: 39.6 MB, less than 28.85% of Java online submissions for Valid Anagram.

效率可谓是极差, 但是思路比较简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isAnagram(String s, String t) {
        Map map = str2Map(s);
        Map map2 = str2Map(t);
        return map.equals(map2);
    }
    private Map str2Map(String s){
        Map<Character, Integer> map = new HashMap<>();
        for (char m : s.toCharArray()) {
            if (map.containsKey(m)){
                map.put(m, map.get(m)+1);
            }else{
                map.put(m, 1);
            }
        }
        return map;
    }
}

Solution3 best one–str转array，再用数组统计次数

思路：解法类似于boomfilter判断一个数是否存在过一样。字母只有26位，初始化一个26位的数组，然后将其ascii码减去‘a’的ascii码，计算出在数组中的位置，然后执行+1操作

另一个数组，同上，但是执行-1操作。如果两字符串相同，则数组最终为26个0。

Runtime: 1 ms, faster than 100.00% of Java online submissions for Valid Anagram.

Memory Usage: 38.9 MB, less than 96.44% of Java online submissions for Valid Anagram.

Time Complexity: O(n)

Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
                return false;
            }
            int[] arr = new int[26];
            for (char m : s.toCharArray()) {
                arr[m - 'a'] += 1;
            }
            for (char m : t.toCharArray()) {
                arr[m - 'a'] -= 1;
            }
            for (int i : arr) {
                if (i != 0) {
                    return false;
                }
            }
            return true;
        }
}