LeetCode #242: Valid Anagram

LeetCode Solutions

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

This problem requires you to determine whether two given strings are anagrams of each other or not. An anagram is a word or phrase formed by rearranging the letters of another word or phrase. In this case, if the two strings contain the same characters, in the same frequency, then they are considered anagrams.

To solve this problem in Python 3, you can follow these steps:

  1. Create a function called “is_anagram” that takes two string arguments.
  2. Check if the lengths of the two strings are the same. If they are not, return false since they cannot be anagrams.
  3. Create two dictionaries to store the frequency of each character in the two strings.
  4. Iterate through the characters in the first string and add their frequency to the s_dict dictionary. The syntax s_dict.get(c, 0) + 1 essentially tries to access the ‘c’ key in s_dict, but if it is not there, it will default the value to 0. In this way, you can concisely write if the key doesn’t exist, default to 0 and add 1, else you just grab the value and add 1.
  5. Iterate through the characters in the second string and add their frequency to the t_dict dictionary.
  6. Compare the two dictionaries to check if they have the same frequency of each character. If they are not the same, return false; otherwise, return true.

Here’s the complete solution:

class Solution:
    def isAnagram(self, s, t):
        if len(s) != len(t):
            return False

        s_dict, t_dict = {}, {}

        for c in s:
            s_dict[c] = s_dict.get(c, 0) + 1

        for c in t:
            t_dict[c] = t_dict.get(c, 0) + 1

        return s_dict == t_dict

Space Complexity:

We use two dictionaries to store the frequency of each character in the two input strings. The space complexity of this approach is O(n), where n is the length of the strings. This is because the space required to store the dictionaries increases linearly with the length of the strings.

Runtime Complexity:

We use two dictionaries to store the frequency of each character in the two input strings. The runtime complexity of this approach is O(n), where n is the length of the strings. This is because we need to iterate over both strings once to build the dictionaries. The time required to build a dictionary is O(1), so the overall time complexity of building two dictionaries is O(n).

After building the dictionaries, we need to compare them to determine if the two strings are anagrams. Comparing two dictionaries takes O(n) time because we need to iterate over one of the dictionaries and check if each key in it is present in the other dictionary. The worst-case scenario is when all the keys in one dictionary are also in the other dictionary, which takes O(n) time.