Description
Decide whether two lowercase English strings contain the same letters with the same multiplicities.
Solution
def is_anagram(s, t):
if len(s) != len(t):
return False
counts = [0] * 26
for a, b in zip(s, t):
counts[ord(a) - 97] += 1
counts[ord(b) - 97] -= 1
return all(x == 0 for x in counts)Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
["tea","eat"]- Output
true
Both strings contain one t, e, and a.
Example 2
- Input
["aab","abb"]- Output
false
The counts of a and b differ.
Example 3
- Input
["a","aa"]- Output
false
The lengths differ.
Approach
Count letters in one string and subtract the other string's counts.
Time & space
O(n + m) time; O(1) space for the fixed 26-letter alphabet.