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

By Manas | 11 February 2021

February LeetCoding Challenge 2021

Day 11

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)

Follow up
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.

code

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[26] = {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;
    }
};

LEAVE A COMMENT

If you like the post leave a comment and share it.

Leave a Reply