242. Valid Anagram

四刷 07/2022

Version #1 Array as HashMap

Time O(M + N)

Space O(26)~O(1)

Runtime: 3 ms, faster than 95.30% of Java online submissions for Valid Anagram.

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

class Solution {

    public boolean isAnagram(String s, String t) {

        if (s.length() != t.length()) {

            return false;

        }

        int[] count = new int[26];

        for (int i = 0; i < s.length(); i++) {

            count[s.charAt(i) - 'a']++;

        }

        for (int i = 0; i < t.length(); i++) {

            int index = t.charAt(i) - 'a';

            if (count[index] == 0) {

                return false;

            }

            count[index]--;

        }

        return true;

    }

}

Using a int array as a hash table to count every character of string t
Check if number count of string s matches the hash table, if not, return false.

LeetCode Great Explanation
To examine if $t$ is a rearrangement of $s$, we can count occurrences of each letter in the two strings and compare them. Since both $s$ and $t$ contain only letters from $a-z$, a simple counter table of size 26 is suffice.

Follow up

What if the inputs contain unicode characters? How would you adapt your solution to such case?

Answer

Use a hash table instead of a fixed size counter. Imagine allocating a large size array to fit the entire range of unicode characters, which could go up to more than 1 million. A hash table is a more generic solution and could adapt to any range of characters.

28.68%
public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s == null || t == null || s.length() != t.length()) return false;
        int[] hash = new int[26];
        for (int i = 0; i < t.length(); i++) {
            hash[t.charAt(i) - 'a']++;
        }
        int index;
        for (int j = 0; j < s.length(); j++) {
            if (--hash[s.charAt(j) - 'a'] < 0) return false;
        }
        for (int k = 0; k < hash.length; k++) {
            if (hash[k] != 0) return false;
        }
        return true;
    }
}


二刷
42.21 %
public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s == null || t == null) throw new IllegalArgumentException();
        int[] hash = new int[256];
        int i = 0;
        for (i = 0; i < s.length(); i++) {
            hash[s.charAt(i)]++;
        }
        for (i = 0; i < t.length(); i++) {
            hash[t.charAt(i)]--;
        }
        for (int count : hash) {
            if (count != 0) return false;
        }
        return true;
    }
}

三刷
85.47 %
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s == null || t == null || s.length() != t.length()) return false;
        int len = s.length();
        int[] count = new int[256];
        for (int i = 0; i < len; i++) {
            count[s.charAt(i) - 'a']++;
        }
        for (int j = 0; j < len; j++) {
            count[t.charAt(j) - 'a']--;
        }
        for (int k = 0; k < count.length; k++) {
            if (count[k] != 0) return false;
        }
        return true;
    }
}