Check if two words use exactly the same letters. Count up for every letter in one, count down for the other, and see if every tally hits zero.
▼The problem
LeetCode 242 (Easy). Given two strings s and t (lowercase letters), return true if t is an anagram of s: the same letters, each the same number of times, in any order.
Examples: s = "anagram", t = "nagaram" → true; s = "rat", t = "car" → false.
The solution
def isAnagram(s, t):
if len(s) != len(t):
return False
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
for c in t:
count[ord(c) - ord('a')] -= 1
return all(x == 0 for x in count)Transcript
Valid Anagram. Given two strings, s and t, return true if t is an anagram of s: the same letters, the same number of times, in any order.
Take anagram and nagaram. Each has three a's, and one each of n, g, r and m. True. But rat and car? Car has a c instead of a t. False.
The naive way sorts both strings and compares them. It works, but sorting costs n log n. Searching t for each letter of s is even worse: n squared.
Better: just count. Keep a jar for each letter, twenty six in all. Every letter of s drops a candy into its jar. Every letter of t takes one out. If all the jars end up empty, it's an anagram. Check the lengths first: different lengths can never match.
In code: compare the lengths, make twenty six counters, add one for each letter of s, subtract one for each letter of t, and return whether all are zero.
On the example, anagram fills the a jar to three and four more jars to one. Nagaram empties every jar: all zero, true. For rat and car, the t jar keeps a candy and the c jar drops below zero. False.
Each string is read once, so time is order n. There are twenty six counters at any length, so space is order one.
Count up, count down, check for zero. That's Valid Anagram.