LeetCode 242 - Valid Anagram

https://leetcode.com/articles/valid-anagram/

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

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

O(nlogn)

An anagram is produced by rearranging the letters of s into t. Therefore, if t is an anagram of s, sorting both strings will result in two identical strings. Furthermore, if s and t have different lengths, t must not be an anagram of s and we can return early.

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    char[] str1 = s.toCharArray();
    char[] str2 = t.toCharArray();
    Arrays.sort(str1);
    Arrays.sort(str2);
    return Arrays.equals(str1, str2);
}

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.

Do we need two counter tables for comparison? Actually no, because we could increment the counter for each letter in s and decrement the counter for each letter in t, then check if the counter reaches back to zero.

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

Or we could first increment the counter for s, then decrement the counter for t. If at any point the counter drops below zero, we know that t contains an extra letter not in s and return false immediately.

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] table = new int[26];
    for (char c : s.toCharArray()) {
        table[c - 'a']++;
    }
    for (char c : t.toCharArray()) {
        table[c - 'a']--;
        if (table[c - 'a'] < 0) return false;
    }
    return true;
}

https://leetcode.com/discuss/76792/o-n-java-simplest-solution
int count1[] = new int[26]; int count2[] = new int[26]; if(s.length()!=t.length()) return false; for(int i=0;i<s.length();i++){ count1[(s.charAt(i) - 'a')]++; count2[(t.charAt(i)-'a')]++; } if(Arrays.equals(count1,count2)) return true; else return false; }
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.

https://leetcode.com/discuss/49787/3-solutions-sort-hash-array-and-prime

Use primes to generate hashcode.

private static final int[] PRIMES = new int[]{3, 5, 7, 11 ,13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 107}; public boolean isAnagram(String s, String t) { return hash(s) == hash(t); } private long hash(String s) { long hash = 1; for (int i = 0; i < s.length(); i++) { hash *= PRIMES[s.charAt(i) - 'a']; } return hash; }