Question. Valid Anagram (from LC 242)
Given two strings s
and t
, return true
if t
is an anagram of s
, and false
otherwise.
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.
Understanding
Firstly, what is the anagram? For example, ‘not’ and ‘ton’ are anagram. ‘not’ and ‘nnt’ is not an anagram. Let’s think of some cases/rules to consider.
- Different lengths of words: If two given words have different lengths (a word length is longer than another one), they can’t be an anagram.
- The number of contained characters must be the same count. For example, ‘sss’ contains 3 ‘s’s, but ‘ssi’ contains 2 's’s and 1 ‘i’. so they are not an anagram.
Approach
- Sorting
I believe sorting is the most intuitive approach for this question. Sort both given words, and compare two words to make sure they are exactly the same.
There are some built-in functions that are needed.
len()
function
returns the length of the given string, array, list, tuple and dictionary. (other languages use the many functions for length check — size(), length() etc.. but python has only one function!)
False and True
For boolean expression, Python uses False
and True
rather than false and true.
sorted()
function
sorted() returns an ordered list in numbers or strings. sorted() can be used to the array, list, tuple and set, but the output is always list since sorted returns a new list. (resources: https://realpython.com/python-sort/)
- sorted(‘anagram’) will return [‘a’, ‘a’, ‘a’, ‘g’, ‘m’, ’n’, ‘r’]
- sorted([6, 8, 3, 1]) will return [1, 3, 6, 8]
2. Write the code
After I looked up all the necessary functions to use, I start to write the code.
class Solution(object):
def isAnagram(self, s, t):
if len(s) != len(t):
return False
else:
if sorted(s) == sorted(t):
return True
else:
return False
"""
:type s: str
:type t: str
:rtype: bool
"""
The first if condition covered the case for the Different lengths of words, and else case covered the rest of the cases.
Because python supports a list comparison, I wrote if sorted(s) == sorted(t): . (It surprised me because I originally tried to compare two array index by index with a loop.)
3. Complexity
Time Complexity: O(nlogn) — due to the sorted() function. len() function is O(n) so it will be 2n + 2nlogn in specific.
Space Complexity: O(1) — no extra space needed. So it’s constant.
4. Shorter version
Python supports the ternary operator, so wrote a shorter version the above function. (resource: https://www.geeksforgeeks.org/ternary-operator-in-python/)
[on_true] if [expression] else [on_false]
class Solution(object):
def isAnagram(self, s, t):
if len(s) != len(t):
return False
else:
return (True if sorted(s) == sorted(t) else False)
or even shorter.
class Solution(object):
def isAnagram(self, s, t):
return (False if len(s) != len(t) else
(True if sorted(s) == sorted(t) else False))
Anagram can be solved with O(n+m) time complexity with a hashmap, (probably with a dictionary in python).
For learning purposes, I’ll leave this for the next time. :)