242. Valid Anagram

Given two stringssandt, write a function to determine iftis an anagram ofs.

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:

This one can be solved by using char Array, HashMap to count the number of occurrence of each characters.

Or using sort. Quick sort or merge sort both are fine and yield a constant space but slower computation.

Complexity: (QuickSort)

Time: O(nlogn)

Space: O(logn)

Code:

public class Solution {
    //Quick sort solution
    public boolean isAnagram(String s, String t) {

        if(s == null || t == null || s.length() != t.length()){
            return false;
        }
        if(s.isEmpty() && t.isEmpty()){
            return true;
        }

        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();

        qs(ss, 0, ss.length - 1);
        qs(tt, 0, tt.length - 1);

        for(int i = 0; i < ss.length; i++){
            if (ss[i] != tt[i]){
                return false;
            }
        }
        return true;
    }

    private void qs(char[] chars, int s, int e){
        if(s >= e){
            return;
        }

        int index = partition(chars, s, e);
        qs(chars, s, index-1);
        qs(chars, index, e);
    }

    private int partition(char[] chars, int s, int e){
        int m = (s+e)/2;
        char pivot = chars[m];
        while(s <= e){
            while(chars[s] < pivot) s++;
            while(chars[e] > pivot) e--;
            if(s <= e){
                char temp = chars[s];
                chars[s] = chars[e];
                chars[e] = temp;
                s++;
                e--;
            }
        }
        return s;
    }
}