Leetcode specifications

Here it comes with another Leetcode problem. And this time it is also an easy problem.

Question: Valid Anagram

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.

Example:

Input: s = "anagram", t = "nagaram"
Output: true
Input: s = "rat", t = "car"
Output: false

Constraints:

1 <= s.length, t.length <= 5 * 10``4

s and t consist of lowercase English letters.

Thought process

n = length of s m = length of t

Brute force - O(mn)

One way to solve this problem is to compare each letter in s with each letter in t to see if they are anagrams, and vice versa. However, this would result in a time complexity of O(mn), which is not efficient for large inputs, and it will cause Time Limit Exceed (TLE). Therefore, we need to come up with a more efficient algorithm to solve this problem.

def isAnagram(self, s: str, t: str) -> bool:
    s_compared, t_compared = [False for _ in range(len(s))], [False for _ in range(len(t))]
    for char in s:
        has_same_char = False
        for i in range(len(t)):
            if t[i] == char and not t_compared[i]:
                t_compared[i], has_same_char = True, True
                break
        if not has_same_char:
            return False
    for char in t:
        has_same_char = False
        for i in range(len(s)):
            if s[i] == char and not s_compared[i]:
                s_compared[i], has_same_char = True, True
                break
        if not has_same_char:
            return False
    return True

Use of sorting - O(m log(m) + n log(n))

Looping the string all over again is inefficient. If we can compare two strings side by side with the same condition, we can reduce the time to O(n). Therefore, in order to make two strings in the same condition, we can use sorting to achieve this.

We can sort both strings and then compare them. If they are equal, then t is an anagram of s. Otherwise, it is not. The time complexity of this algorithm is O(m log(m) + n log(n)), which is more efficient than the brute force algorithm.

def isAnagram(self, s: str, t: str) -> bool:
    return sorted(s) == sorted(t)

Use of hash map - O(m+n)

One more efficient algorithm to solve this problem is to use hash maps. We can create a hash map for each string and store the frequency of each letter in the respective hash map, or we can use the built-in class Counter to do the same job. Then, we can compare the hash maps to see if they are equal. If they are equal, then t is an anagram of s. Otherwise, it is not. The time complexity of this algorithm is O(m+n), which is much more efficient than the brute force and sorting algorithms..

from collections import Counter

def isAnagram(self, s: str, t: str) -> bool:
    s_counter, t_counter = Counter(s), Counter(t)
    ans = True
    if s_counter != t_counter:
        ans = False
    return ans

Take away

The use of a hash map in solving this problem is much more efficient than the brute force algorithm, as it reduces the time complexity from O(mn) to O(m+n). Therefore, it is recommended to use a hash map to solve this problem.

In fact, when we involve in different Leetcode problems, a hash map is basically the first method I will try to solve the problem efficiently as we can search a specific key-value pair in just O(1) time, which is very efficient. However, we need to ensure that the key-value pairs we use are unique and that we are not overusing memory. Moreover, while a hash map is efficient, it is not always the best solution for every problem. Therefore, it is important to understand the problem's requirements and constraints before choosing the best algorithm to solve it.