Valid Anagram

Question

Given two strings s and t, write a function to determine if t is an anagram of s.

For example, s = "anagram", t = "nagaram", return true. s = "rat", t = "car", return false.

Note: You may assume the string contains only lowercase alphabets.

Tags

• Hash Table
• Sort

Thought

Two solutions:

• hash table
• sort

Use the hash table to store the frequency of the characters in the string and the time complexity is O(N).

Or you can sort the two string and compare them. The time complexity is O(NlogN)

Code

class Solution(object):
    def isAnagram(self, s, t):
        """
        Use hash table here to count the frequency of the characters in a word and check it with another word.


        :type s: str
        :type t: str
        :rtype: bool
        """
        ch_dict = {}
        for ch in s:
            if ch not in ch_dict:
                ch_dict[ch] = 1
            else:
                ch_dict[ch] += 1

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

        return len(ch_dict) == 0