LeetCode - Algorithms - 242. Valid Anagram

Problem

242. Valid Anagram

Java

HashMap

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
class Solution {
    public boolean isAnagram(String s, String t) {
        final int len_s = s.length();
        final int len_t = t.length();
        if (len_s != len_t)
            return false;
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            Character k = s.charAt(i);
            if (map.containsKey(k)) {
                Integer num = map.get(k);
                map.put(k, ++num);
            }
            else {
                map.put(k, 1);
            }
        }
        for (int i = 0; i < t.length(); i++) {
            Character k = t.charAt(i);
            if (map.containsKey(k)) {
                Integer num = map.get(k);
                map.put(k, --num);
            } else {
                return false;
            }
        }
        for (Integer count : map.values()) {
            if (count.intValue() != 0)
                return false;
        }
        return true;
    }
}

Submission Detail

  • 34 / 34 test cases passed.
  • Runtime: 12 ms, faster than 22.04% of Java online submissions for Valid Anagram.
  • Memory Usage: 40.6 MB, less than 28.82% of Java online submissions for Valid Anagram.

Sorting

© 20+ basic Algorithms Problems from Coding Interviews 16. Write Algorithms to Check if Two String are Anagram

One trick to solve this problem is to sort the character array and check if they are the same or not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isAnagram(String s, String t) {
        final int len_s = s.length();
        final int len_t = t.length();
        if (len_s != len_t)
            return false;
        char[] arr_s = s.toCharArray();
        char[] arr_t = t.toCharArray();
        Arrays.sort(arr_s);
        Arrays.sort(arr_t);
        for (int i = 0; i < len_s; i++) {
            if (arr_s[i] != arr_t[i])
                return false;
        }
        return true;
    }
}

Submission Detail

  • 34 / 34 test cases passed.
  • Runtime: 4 ms, faster than 51.35% of Java online submissions for Valid Anagram.
  • Memory Usage: 42.2 MB, less than 9.92% of Java online submissions for Valid Anagram.

leetcode solution - Hash Table

It seemed that no 0ms solution by java.

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) {
        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;
    }
}

Submission Detail

  • 34 / 34 test cases passed.
  • Runtime: 3 ms, faster than 79.53% of Java online submissions for Valid Anagram.
  • Memory Usage: 39.4 MB, less than 84.32% of Java online submissions for Valid Anagram.