Leetcode 242 Valid Anagram

Leetcode 242 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?

 Analysis:

Anagram (易构词，变位词) is a kind of word, which can produce a new word, after rearranging the order of the characters.

Note: if the length of the two strings are not the same, they’re not anagrams. 

Method 1:

We can try to sort the two arrays and then compare them, if they’re equal to each other, they’re anagrams, vise versa.

        
        if (s.length() != t.length()) {
            return false;
        }
        
        char[] ary1 = s.toCharArray();
        char[] ary2 = t.toCharArray();
        
        Arrays.sort(ary1);
        Arrays.sort(ary2);
        
        return Arrays.equals(ary1, ary2);

Here we should be aware the usage of Arrays. We first need to convert the string to a char array, because the parameter for Array.sort() method is char array. Then we can use the Array.equals method to check whether the two arrays are equal to each other.

Note: For this method, we need to import java.util.Arrays.

Time complexity: O(nlogn + n) = O(nlogn)

Space complexity: O(1)

Assume n is the length of s, then sorting algorithm cost O(nlogn), and comparing two strings cost O(n). The sorting dominates, then it requires O(nlogn).

Method 2:

If method 1 is not allowed, we can try another way. We can count the 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? No!

We could use one table to increase the counter for each letter in s and decrease the counter for each letter in t, then check if the counter reaches back to zero.

        int[] counts = new int[26];
        
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i) - 'a']++;
            counts[t.charAt(i) - 'a']--;
        }
        
        for (int count: counts) {
            if (count != 0) {
                return false;
            }
        }
        
        return true;

Or we can first increase the counter for s, then decrease the counter for t. If at any point that counter for t is below 0, we know that there’s other element in t that does not belong to s. The code is:

        int[] count = new int[256];
        
        for (int i = 0; i < s.length(); i++) {
            count[(int) s.charAt(i)]++;
        }
        
        for (int i = 0; i < t.length(); i++) {
            count[(int) t.charAt(i)]--;
            if (count[(int) t.charAt(i)] < 0) {
                return false;
            }
        }
        
        return true;

Time complexity: O(n)
Space complexity: O(1)

Accessing the counter table is constant time, so it’s O(n). For the space, we do have extra counter table. However, its size is fixed, so it’s O(1).

Follow up: what if the inputs contains unicode characters?

Use HashTable instead of counter array.