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 s1Example 1
Input
s0 = “listen”
s1 = “silent”
Output
TrueExample 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:
1 2 3 4 5 6 7 | 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 |
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:
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 | 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 |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | 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 |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 | 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 |
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:
1 2 3 4 5 | form collections import Counter class Solution: def solve(self, s0, s1): return Counter(s0) == Counter(s1) |
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) —
loading...
Last Post: Unique Occurrences Algorithms for Numbers
Next Post: Depth First Search and Breadth First Search Algorithm to Compute the Left Side View of a Binary Tree