242. Valid Anagram

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

Solution in python:

1. Sort (can’t pass the last case)

   class Solution:
   def isAnagram(self, s: str, t: str) -> bool:
       def quicksort(arr, l, r):
           # if clause is important in recursion
           if l < r:
               pivot = arr[l]
               i, j = l, r 
   
               while i < j:
                   # don't forget the '='
                   while i < j and arr[j] >= pivot:
                       j -= 1
   
                   arr[i] = arr[j]
   
                   while i < j and arr[i] <= pivot:
                       i += 1
   
                   arr[j] = arr[i]
   
                   arr[i] = pivot
   
               quicksort(arr, l, i-1)
               quicksort(arr, i+1, r)
   
       len_s, len_t = len(s), len(t)
       strarr_s, strarr_t = list(s), list(t)
       quicksort(strarr_s, 0, len_s-1)
       quicksort(strarr_t, 0, len_t-1)
   
       if strarr_s == strarr_t: return True
       else: return False

   Complexity analysis:

   • Time complexity: O(n\log_{}n)
   • Space complexity: O(n)
2. Hash

   class Solution:
   def isAnagram(self, s: str, t: str) -> bool:
       a = [0 for i in range(26)]
       for cha in s:
           a[ord(cha)-97] += 1
       for cha in t:
           a[ord(cha)-97] -= 1
           if a[ord(cha)-97] < 0:
               return False
       if sum(a):
           return False
       else: return True

   Complexity analysis:

   • Time complexity: O(n)
   • Space complexity: O(1)