242. Valid Anagram — LeetCode(Python)
I got you!
Problem:
Given two strings s
and t
, return true
if t
is an anagram of s
, and false
otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Constraints:
1 <= s.length, t.length <= 5 * 104
s
andt
consist of lowercase English letters.
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
Solution:
s_dict, t_dict = {}, {}
for c in s:
if c in s_dict:
s_dict[c] += 1
else:
s_dict[c] = 1
for c in t:
if c in t_dict:
t_dict[c] += 1
else:
t_dict[c] = 1
return s_dict == t_dict
Explanation —
We create a dictionary for both strings and return true if both dictionaries are the same, false otherwise.
Time Complexity —
Creating a dictionary and checking if they are same takes linear time and space.
Thus, if n is the number of characters in s,
Time Complexity: O(n)
Space Complexity: O(n)