0242. Valid Anagram

Problem Category:: Array, Hash table Neetcode Category:: Arrays and Hashing

https://leetcode.com/problems/valid-anagram/

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

Optimal

Dictionary (hash table)

Use a hash table based data structure, such as Dictionary. Store letter frequencies using the letter as the key

• Increment for the first word and decrement for the second so that we can use just one dictionary
• $2nO(1)$ dictionary puts/edits, $O(2n)$ dictionary traversal → $O(n)$ time complexity
• $O(n)$ space complexity

Example Python code

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        dictionary = {}
        for letter in s:
            if letter not in dictionary:
                dictionary[letter] = 1
            else:
                dictionary[letter] += 1
                
        for letter in t:
            if letter not in dictionary:
                return False
            else:
                dictionary[letter] -= 1
                # Decrement value - we avoid using 2 dicts this way
                
        for value in dictionary.values():
            if value != 0:
                return False
        
        return True

Others

Sort and compare

• Time complexity: $O(nlog(n))$
  • Sort the characters in both strings: $O(nlog(n))$
  • Compare the two lists $O(n)$
• Space complexity: $O(n)$ (reducible to $O(1)$ when using methods that avoid duplication)

Example

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
	    return sorted(s) == sorted(t) # O(n) space due to strings being immutable

Python sorted()

Unlike list.sort(), the sorted() function works on any iterable, including strings, so we don’t have to split

• However, sorted() makes a copy, unlike list.sorted(). For our immutable strings, this is desired