## Sunday, March 27, 2016

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