algoadvance

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

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.

Clarifying Questions

  1. Q: Are the inputs always valid strings?
    • A: Yes.
  2. Q: Is the comparison case-sensitive?
    • A: Yes, the comparison is case-sensitive.
  3. Q: Can the strings contain spaces or special characters?
    • A: Yes, they can contain any characters.

Strategy

To determine if t is an anagram of s:

  1. Both strings must have the same length.
  2. Both strings must contain the exact same characters with the same frequencies.

We can implement this using two strategies:

  1. Sorting: Sort both strings and compare them. If they are identical after sorting, one is an anagram of the other.
  2. Hash Map (Dictionary): Use a dictionary to count the frequency of each character in both strings. Then compare the two dictionaries.

The hash map strategy is more efficient because sorting has a time complexity of O(n log n), while using a hash map has a linear time complexity of O(n).

We’ll implement the hash map strategy.

Code

def isAnagram(s: str, t: str) -> bool:
    # Early return if lengths differ
    if len(s) != len(t):
        return False
    
    # Create frequency dictionaries for both strings
    count_s = {}
    count_t = {}
    
    for char in s:
        count_s[char] = count_s.get(char, 0) + 1
    
    for char in t:
        count_t[char] = count_t.get(char, 0) + 1
    
    # Compare frequency dictionaries
    return count_s == count_t

Explanation

  1. Early Return: If the lengths of s and t are different, immediately return False.
  2. Frequency Dictionaries: Create dictionaries to count the occurrences of each character in both s and t.
  3. Comparison: Compare the two dictionaries. If they are equal, then t is an anagram of s; otherwise, it is not.

Time Complexity

Try our interview co-pilot at AlgoAdvance.com