Learning Python with Interview Questions 2. Anagram

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 and t consist of lowercase English letters.

Anagram

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

1. 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. :)