The posts in this series (each with the tag Bloomberg
) contain problems taken from this list of Bloomberg phone interview problems. In this post, we solve LeetCode’s 242 Valid Anagram.
Given two strings s and t , write a function to determine if t is an anagram of s.
First, it’s important to know the difference between an anagram and a palindrome. An anagram is a word formed by rearranging the letters of another word. So if string s
is “tarp” and string t
is “part”, then s
and t
are anagrams of one another. On the other hand, A palindrome is a word that reads the same backward or forward (like the word “kayak”).
There are a couple of ways to tackle this problem. Each approach involves creating a dictionary where the letters from s
and t
are keys and the values are counts of how many times the letters occur in the string. Whenever we create a tally dictionary in Python, we have to be cognizant of avoiding KeyError
s. The first approach relies on python’s .get()
method to avoid this, while the last two methods rely on the Python’s collections
classes.
Solution using Dictionary and .get()
¶
In Python, the get(key, default)
method returns a value for the given key in a dictionary. If key
is not available, the method then returns default
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
Solution using collections.defaultdict
¶
The defaultdict
class is covered in the Stacks, Queues, Heaps, and Hash Tables in Python post. Where a Python dictionary normally throws a KeyError
if you try to retrieve a value with a key that is not in the dictionary, defaultdict
will just create a new key-value pair with a default value.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
Solutions using collections.Counter
¶
Like defaultdict
, the Counter
class is also a subclass of Python Dictionary. It’s a class designed to keep tallies, like we are doing here.
1 2 3 4 5 6 7 8 9 10 11 12 |
|