How to Check If Two Words Are Anagrams in Python

How to Check if Two Words are Anagrams in Python

Clarity and precision are essential in solving coding problems efficiently.

Today, we'll explore two alternative solutions to a common coding challenge: determining if two words, or strings, are anagrams.

We'll analyze both approaches, improve them where possible, and break down every step to ensure you can follow along effortlessly.

What Is an Anagram?

When you rearrange the exact letters already forming another word -> the resultant word formed is an anagram.

For example, "listen" and "silent" are anagrams because they contain the same letters in different order.

Our task is to write a function that checks whether two given strings are anagrams of each other.

Here are two approaches to solving the problem.

Using Sorting

Sort the characters in both strings and compare the results.

# Code Example

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # Sort both strings alphabetically
        sorted_s = sorted(s)
        sorted_t = sorted(t)
        
        # Compare sorted strings
        return sorted_s == sorted_t

Explanation

Sorting Strings: The sorted() function arranges the characters of the string alphabetically. For example, sorted("silent") returns ['e', 'i', 'l', 'n', 's', 't'].
Comparison: If the sorted versions of s and t are identical, the strings are anagrams. Otherwise, they are not.

Time Complexity: O(n log n)

Sorting the strings is the most time-consuming step.

Space Complexity: O(n)

The sorted() function creates new lists to hold the sorted characters.

Using Frequency Counts

The second solution compares the frequency of each character in the two strings.

# Code Example
class Solution:

    def isAnagram(self, s: str, t: str) -> bool:
      """
        Args:
            s(str): first string
            t(str): second string
        Returns:
            (bool): response if the two strings are anagrams
      """
        # Not anagrams
        if len(s) != len(t):
            return False
        
        # Each character's frequency
        for char in s:
            if s.count(char) != t.count(char):
                return False
        
        return True

Explanation

Length Check: Avoids unnecessary calculations if s's and t's lengths differ.
Counting Characters: For each character in s, we count how many times it appears in both strings using the count() method. If the counts don't match, the strings are not anagrams.

Time Complexity: O(n²)

The count() method is called for each character in s, and it scans the entire string t, making it inefficient for large inputs.

Space Complexity: O(1)

The solution doesn't create any extra data structures.

Optimized Approach: Using a Hash Map (Dictionary)

Both solutions can be improved to achieve better performance, especially when handling large strings.

Instead of sorting or repeatedly counting characters, use dict's to count the frequency of each character.

# Optimized Code Example
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        """
        Determine if two strings are anagrams using character frequency counts.

        Args:
            s (str): The first string.
            t (str): The second string.

        Returns:
            bool: True if the strings are anagrams, False otherwise.
        """

        # If lengths differ, they can't be anagrams
        if len(s) != len(t):
            return False

        # Use a dictionary to count characters in `s`
        char_count = {}
        for char in s:
            char_count[char] = char_count.get(char, 0) + 1

        # Subtract character counts using `t`
        for char in t:
            if char not in char_count or char_count[char] <= 0:
                return False
            char_count[char] -= 1

        return True

Why This Approach Is Better

Efficient Counting:  Using a dictionary allows us to count characters in O(n) time.
Avoids Sorting Overhead:  Sorting strings is unnecessary, saving time and space.

Time Complexity: O(n)

We traverse each string once.

Space Complexity: O(n)

The dictionary stores up to n unique characters.

Comparing the Solutions

Approach                             Time Complexity                          Space Complexity            Best Use Case                     

Sorting                                           O(n log n)                                     O(n)                            Small or medium-sized strings    
Frequency Count (Naïve)            O(n²)                                              O(1)                            Short strings with fewer characters    
Hash Map Optimization              O(n)                                               O(n)                            Large strings or performance-critical tasks    

Why Optimization Matters

In real-world applications, especially those involving large datasets or repeated operations, optimizing algorithms can significantly improve performance.

The optimized solution we explored today ensures the problem is solved in linear time while maintaining clarity and robustness.

What's Next?

Understanding the trade-offs between different approaches is key to becoming a better problem solver.

Now that you've seen multiple ways to solve the anagram problem try applying similar optimization techniques to other challenges.

Start experimenting with dictionaries, sets, and other data structures in Python to further enhance your skills.