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

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)
最后修改日期: 2020年9月11日