242_Valid Anagram

Level: easy

Tag: string, sort, hash table

Question

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

What is Anagram?
- Two strings are anagram if they can be the same after change the order of characters.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return 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?

Idea

If s and t have different lengths, t must not be an anagram of s and we can return early.

For the main body of the algorithm, there are several solutions with different time complexity.

1. Sort both strings and compare them. If t is an anagram of s, sorting both strings will result in two identical strings.

2. Count occurrences of each letter in the two strings, store in dictionary, and compare two dictionaries. If t is an anagram of s, the two dictionaries should be equal.

Complexity 1

• Time complexity :$O(n logn)$. Assume that n is the length of sand t , sorting costs $O(nlogn)$ and comparing two strings costs $O(n)$ . Sorting time dominates and the overall time complexity is $O(nlogn)$ .

• Space complexity : $O(1)$ . Space depends on the sorting implementation which, usually, costs O(1) auxiliary space if heapsortis used.

Complexity 2

• Time complexity :$O(n)$. Because we access each letter only once.

• Space complexity : $O(1)$ . Because at most we have 26 various letters to store in the dictionary. It's a constant as the length of s and t increase.

Solution 1 (sort)

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """

        # check if the length of s and t is different
        if len(s) != len(t) :
            return False

        # check if sorted s and sorted t is the same
        return sorted(s) == sorted(t)

Solution 2 (no sort, using dictionary)

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """

        # check if the length of s and t is different
        if len(s) != len(t) :
            return False

        # create two dictionaries to store the letters and their frequences
        dic1, dic2 = {}, {}
        for item in s:
            dic1[item] = dic1.get(item, 0) + 1
        for item in t:
            dic2[item] = dic2.get(item, 0) + 1
        return dic1 == dic2

Solution 3 (no sort, using count table, same time/space complexity as solution 2)

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """

        # check if the length of s and t is different
        if len(s) != len(t) :
            return False

        # create two count tables to store the counts for 26 letters
        list1, list2 = [0]*26, [0]*26
        for item in s :
            list1[ord(item) - ord("a")] += 1
        for item in t :
            list2[ord(item) - ord("a")] += 1
        return list1 == list2

Questions

1. What if the inputs contain unicode characters?