LC 242 - Valid Anagram

Question

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Constraints:

• 1 <= s.length, t.length <= 5 * 104
• s and t consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Links

Question here and solution here

Solution

concept

We use a hash map to keep track the char in each string, then we compare them afterwards.

code

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        char_dict = {}

        for c in s:
            if c in char_dict:
                char_dict[c] += 1
            else:
                char_dict[c] = 1

        for c in t:
            if c not in char_dict:
                return False
            else:
                char_dict[c] -= 1
                if char_dict[c] == 0:
                    del char_dict[c]

        return True if len(char_dict) == 0 else False

class NeetSolution1(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        lower space complexity since sometimes we assume sorting do not take up space.
        """
        return sorted(s) == sorted(t)
        
class NeetSolution2(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        space complexity: O(n) or O(s+t) -> stores hash table for s and t
        time complexity: O(n) or O(s+t) -> iterate through s and t
        """
        if len(s) != len(t):
            return False

        s_hash = {}
        t_hash = {}

        for i in range(len(s)):
            s_hash[s[i]] = s_hash.get(s[i], 0) + 1
            t_hash[t[i]] = t_hash.get(t[i], 0) + 1

        if s_hash == t_hash:
            return True
        else:
            return False

Complexity

time: $O(n)$ -> iterate through s and t
space: $O(n)$ -> stores hash table for s and t