242. Valid Anagram

01/**
02Given two strings s and t , write a function to determine if t is an anagram of s.
03
04Example 1:
05
06Input: s = "anagram", t = "nagaram"
07Output: true
08Example 2:
09
10Input: s = "rat", t = "car"
11Output: false
12Note:
13You may assume the string contains only lowercase alphabets.
14
15Follow up:
16What if the inputs contain unicode characters? How would you adapt your solution to such case?
17**/
18
19//Runtime: 40 ms, faster than 6.44% of C++ online submissions for Valid Anagram.
20//Memory Usage: 9.6 MB, less than 5.16% of C++ online submissions for Valid Anagram.
21
22class Solution {
23public:
24    bool isAnagram(string s, string t) {
25        map<char, int> count;
26        
27        for(char c : s){
28            if(count.find(c) == count.end()){
29                count[c] = 1;
30            }else{
31                count[c] += 1;
32            }
33        }
34        
35        for(char c : t){
36            map<char, int>::iterator it = count.find(c);
37            if(it == count.end()){
38                return false;
39            }else if(count[c] > 1){
40                count[c] -= 1;
41            }else{
42                count.erase(it);
43            }
44        }
45        
46        if(count.empty()) return true;
47        return false;
48    }
49};
50
51/**
52Approach #1 (Sorting) [Accepted]
53Algorithm
54
55An anagram is produced by rearranging the letters of ss into tt. Therefore, if tt is an anagram of ss, sorting both strings will result in two identical strings. Furthermore, if ss and tt have different lengths, tt must not be an anagram of ss and we can return early.
56
57public boolean isAnagram(String s, String t) {
58    if (s.length() != t.length()) {
59        return false;
60    }
61    char[] str1 = s.toCharArray();
62    char[] str2 = t.toCharArray();
63    Arrays.sort(str1);
64    Arrays.sort(str2);
65    return Arrays.equals(str1, str2);
66}
67Complexity analysis
68
69Time complexity : O(n \log n)O(nlogn). Assume that nn is the length of ss, sorting costs O(n \log n)O(nlogn) and comparing two strings costs O(n)O(n). Sorting time dominates and the overall time complexity is O(n \log n)O(nlogn).
70
71Space complexity : O(1)O(1). Space depends on the sorting implementation which, usually, costs O(1)O(1) auxiliary space if heapsort is used. Note that in Java, toCharArray() makes a copy of the string so it costs O(n)O(n) extra space, but we ignore this for complexity analysis because:
72
73It is a language dependent detail.
74It depends on how the function is designed. For example, the function parameter types can be changed to char[].
75**/
76
77/**
78Approach #2 (Hash Table) [Accepted]
79Algorithm
80
81To examine if tt is a rearrangement of ss, we can count occurrences of each letter in the two strings and compare them. Since both ss and tt contain only letters from a-za−z, a simple counter table of size 26 is suffice.
82
83Do we need two counter tables for comparison? Actually no, because we could increment the counter for each letter in ss and decrement the counter for each letter in tt, then check if the counter reaches back to zero.
84
85public boolean isAnagram(String s, String t) {
86    if (s.length() != t.length()) {
87        return false;
88    }
89    int[] counter = new int[26];
90    for (int i = 0; i < s.length(); i++) {
91        counter[s.charAt(i) - 'a']++;
92        counter[t.charAt(i) - 'a']--;
93    }
94    for (int count : counter) {
95        if (count != 0) {
96            return false;
97        }
98    }
99    return true;
100}
101Or we could first increment the counter for ss, then decrement the counter for tt. 
102If at any point the counter drops below zero, we know that tt contains an extra letter not in ss and return false immediately.
103
104public boolean isAnagram(String s, String t) {
105    if (s.length() != t.length()) {
106        return false;
107    }
108    int[] table = new int[26];
109    for (int i = 0; i < s.length(); i++) {
110        table[s.charAt(i) - 'a']++;
111    }
112    for (int i = 0; i < t.length(); i++) {
113        table[t.charAt(i) - 'a']--;
114        if (table[t.charAt(i) - 'a'] < 0) {
115            return false;
116        }
117    }
118    return true;
119}
120Complexity analysis
121
122Time complexity : O(n)O(n). Time complexity is O(n)O(n) because accessing the counter table is a constant time operation.
123
124Space complexity : O(1)O(1). Although we do use extra space, 
125the space complexity is O(1)O(1) because the table's size stays constant no matter how large nn is.
126
127Follow up
128
129What if the inputs contain unicode characters? How would you adapt your solution to such case?
130
131Answer
132
133Use a hash table instead of a fixed size counter. 
134Imagine allocating a large size array to fit the entire range of unicode characters, 
135which could go up to more than 1 million. A hash table is a more generic solution and could adapt to any range of characters.
136**/