Leetcode – Valid Anagram Solution in Python

Spread the love

Introduction

The Valid Anagram problem is a common algorithmic challenge on LeetCode and is often encountered in coding interviews. It revolves around the concepts of strings and hashing. In this comprehensive article, we will explore the problem statement, discuss multiple approaches to solve it, and implement these solutions in Python. Furthermore, we will analyze the time and space complexities of each method.

Problem Statement

The problem can be stated as follows:

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

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. For example, the word “listen” is an anagram of “silent”.

Input

  • s: a string
  • t: another string

Output

  • A boolean value indicating whether t is an anagram of s.

Approach 1: Sorting

  1. If the lengths of s and t are different, return False as they cannot be anagrams.
  2. Convert both strings to lists of characters.
  3. Sort both lists.
  4. Compare the sorted lists – if they are the same, s and t are anagrams.
def isAnagram(s, t):
    # If the lengths are different, they cannot be anagrams
    if len(s) != len(t):
        return False
    
    # Convert strings to lists and sort them
    s = sorted(list(s))
    t = sorted(list(t))
    
    # Compare the sorted lists
    return s == t

Time Complexity

The time complexity is O(n log n), where n is the number of characters in the strings. This is because the sorting operation dominates the time complexity.

Space Complexity

The space complexity is O(n) as we create new lists to store the characters of the strings.

Approach 2: Hash Tables

  1. If the lengths of s and t are different, return False.
  2. Create hash tables (or dictionaries) to store the frequency of each character in s and t.
  3. Compare the hash tables. If they are the same, s and t are anagrams.
def isAnagram(s, t):
    # If the lengths are different, they cannot be anagrams
    if len(s) != len(t):
        return False
    
    # Create hash tables for s and t
    count_s = {}
    count_t = {}
    
    # Count the frequency of each character in s
    for char in s:
        count_s[char] = count_s.get(char, 0) + 1
        
    # Count the frequency of each character in t
    for char in t:
        count_t[char] = count_t.get(char, 0) + 1
    
    # Compare the hash tables
    return count_s == count_t

Time Complexity

The time complexity is O(n), where n is the number of characters in the strings.

Space Complexity

The space complexity is O(n) due to the additional hash tables.

Approach 3: Single Hash Table

  1. If the lengths of s and t are different, return False.
  2. Create a hash table to store the frequency of each character in s.
  3. Iterate through each character in t, decrementing its count in the hash table.
  4. Check if all counts are 0 in the hash table.
def isAnagram(s, t):
    # If the lengths are different, they cannot be anagrams
    if len(s) != len(t):
        return False
    
    # Create a hash table for s
    count = {}
    
    # Count the frequency of each character in s
    for char in s:
        count[char] = count.get(char, 0) + 1
    
    # Decrement the count for each character in t
    for char in t:
        count[char] = count.get(char, 0) - 1
        if count[char] < 0:
            return False
    
    # Check if all counts are 0
    return all(value == 0 for value in count.values())

Time Complexity

The time complexity is O(n), where n is the number of characters in the strings.

Space Complexity

The space complexity is O(n) due to the additional hash table.

Conclusion

In this article, we examined the Valid Anagram problem on LeetCode and explored three distinct approaches to solving it – sorting, using two hash tables, and using a single hash table. While the sorting method is simpler, it is less efficient than the hashing methods. The single hash table approach is particularly efficient in terms of both time and space complexity. This problem showcases the power of hash tables in solving problems that involve counting elements or checking the presence of elements in a collection.

Leave a Reply