Leetcode 242 - Valid Anagram
Explanation for Leetcode 242 - Valid Anagram problem, and its solution in Python.
Problem
Example:
1
2
3
4
5
Input: s = "anagram", t = "nagaram"
Output: true
Input: s = "rat", t = "car"
Output: false
Approach
Since our input only consists of lowercase letters, we can use an array of size 26 to count the frequency of each letter in s and t, for every letter in s, we increment the count of the letter in the array, and for every letter in t, we decrement the count of the letter in the array. If s and t are anagrams, the array should be all zeros.
To account for the edge case where s and t are different lengths, we can check if the length of s and t are the same, if not, return false.
Visual representation of the approach:
1
2
3
4
5
6
7
8
9
10
11
s = "anagram", t = "nagaram"
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]
after processing s: count = [3,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0]
after processing t: count = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Since the count array is all zeros, we return true.
s = "rat", t = "car"
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]
after processing s: count = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0]
after processing t: count = [0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0]
Since the count array is not all zeros, we return false.
Here’s the code implementation of the approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# if the length of s and t are not the same, return false
if len(s) != len(t):
return False
# initialize a count array of size 26
count = [0] * 26
# iterate through s and t
for i in range(len(s)):
count[ord(s[i]) - ord('a')] += 1
count[ord(t[i]) - ord('a')] -= 1
# if the count array is all zeros, return true
for num in count:
if num != 0:
return False
return True
Time Complexity and Space Complexity
The time complexity is $ O(n) $ since we are iterating through s and t once.
The space complexity is $ O(26) $ which is $ O(1) $ since the size of the count array is constant.