Valid Anagram

题目描述

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

For example, s = "anagram", t = "nagaram", return true. s = "rat", t = "car", return false.

解题方法

sort

第一种方法是将两个string都sort一下，然后就可以判断是否相同。

• 时间复杂度 O(nlogn)

hashtable

第二种方法是统计两个string中出现过的字母的次数，然后比较是否相同。

• 时间复杂度O(n)
• 空间复杂度O(n)

python的collections module有Counter,可以直接统计字母出现的次数，可以利用

Solution

传统写法

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        dic = {}
        for c in s:
            if c not in dic:
                dic[c] = 1
            else:
                dic[c] += 1

        for c in t:
            if c not in dic:
                return False
            else:
                dic[c] -= 1

        for key in dic:
            if dic[key] != 0:
                return False

        return True

Counter

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        t1 = sorted(collections.Counter(s).items())
        t2 = sorted(collections.Counter(t).items())

        return t1 == t2

Reference