Valid Anagram | February Leetcoding Challenge 2021 | Day 11 Manas Sinha
Developer | Designer

VALID ANAGRAM

PROBLEM  STATEMENT:
Given two strings s and t , write a function to determine if t is an anagram of s.
Example 1
Input: s = "anagram", t = "nagaram"
Output: true
Example 2
Input: s = "rat", t = "car"
Output: 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?

Explanation

1.SORTING
ALGORITHM:
• Sort the two strings.
• Check if they are equal.
Time complexity: Sorting takes O(nlogn) and comparing takes O(n) time. Overall complexity:    O(nlogn)
2.HASH TABLE
ALGORITHM:
• Create a counter table of size 26 (assuming all lowercase alphabets).
• Iterate first string and increase the occurance of the charecter in counter table by 1.
• Iterate second string and decrease the occurance of the charecter in counter table by 1.
• Check the counter table for any non zero values, if none present return true else return false
Time complexity: O(n)

What if the inputs contain unicode characters? How would you adapt your solution to such case?
Use a Hash Table instead of fixed size counter table.

SORTING

class Solution {
public:
bool isAnagram(string s, string t) {
sort(s.begin(),s.end());
sort(t.begin(),t.end());
return s == t;
}
};

HASH TABLE

class Solution {
public:
bool isAnagram(string s, string t) {
int arr = {0};
if(s.length() != t.length()) return false;
for(int i=0;i<s.length();++i){
arr[s[i]-'a']++;
arr[t[i]-'a']--;
}
for(int i : arr)
{
if(i!=0) return false;
}
return true;
}
};