Teaching Kids Programming – How to Check if Two Strings Anagrams?

Teaching Kids Programming: Videos on Data Structures and Algorithms

Anagrams are strings/words that contain the same set of letters and each letter should appear the same number of times. For example: Listen and Silent, Ten and Net.

Anagram: a word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.

Given two strings s0 and s1, return whether they are anagrams of each other. Two words are anagrams when you can rearrange one to become the other. For example, “listen” and “silent” are anagrams.

Constraints
n ≤ 100,000 where n is the length of s0
m ≤ 100,000 where m is the length of s1

Example 1
Input
s0 = “listen”
s1 = “silent”
Output
True

Example 2
Input
s0 = “bedroom”
s1 = “bathroom”
Output
False

Check Anagrams in Python using Sorting

We can sort both strings, and the anagrams will be the exactly after sorted. In Python, we can’t sort the strings directly, however, we can converted to list and then join:

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
                return False
        s = "".join(sorted(s))
        t = "".join(sorted(t))
        return s == t

The time complexity is O(NLogN) due to sorting – assuming the string length is N for both strings.

Check Anagrams in Python using Hash Table (Dictionary)

In Python, the dictionary is annotated in curly braces {}. If you want to access a item in the dictionary, the key must be existent, otherwise an exception will be raised. We can count two strings and put their letters and frequencies in two maps, then we can compare both:

class Solution:
    def solve(self, s0, s1):
        a = {}
        b = {}
        # counting the letters for s0
        for i in s0:
            if i in a:
                a[i] += 1
            else:
                a[i] = 0
        # counting the letters for s1
        for i in s1:
            if i in b:
                b[i] += 1
            else:
                b[i] = 0
        # size different, can't be anagrams
        if len(a) != len(b):
            return False
        # comparing two dictionaries.
        for i in a.keys():
            if not i in b or a[i] != b[i]:
                return False
        for i in b.keys():
            if not i in a or a[i] != b[i]:
                return False
        return True

To check if two dictionaries are equal, we can simply check them by == operator. Thus the above can be further reduced to:

class Solution:
    def solve(self, s0, s1):
        a = {}
        b = {}
        # counting letters for s0
        for i in s0:
            if i in a:
                a[i] += 1
            else:
                a[i] = 0
        # counting letters for s1
        for i in s1:
            if i in b:
                b[i] += 1
            else:
                b[i] = 0
        # comparing two dictionaries
        return a == b

Also, with the usage of defaultdict, we don’t need to check if a key is existent before we update the item, just make sure specify a default type/constructor – which is int type:

from collections import defaultdict

class Solution:
    def solve(self, s0, s1):
        a = defaultdict(int)
        b = defaultdict(int)
        # counting s0
        for i in s0:
            a[i] += 1
        # counting s1
        for i in s1:
            b[i] += 1
        return a == b

Can we do better? In Python, we can count the items using the Counter object:

form collections import Counter

class Solution:
    def solve(self, s0, s1):
        return Counter(s0) == Counter(s1)

The One-liner!

Using Hash Table gives O(N) complexity in both time and space.

–EOF (The Ultimate Computing & Technology Blog) —