創(chuàng)建于20170308
原文鏈接：https://leetcode.com/problems/valid-anagram/?tab=Description

1 題目

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.

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?

2 題解：python

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False
        
        dict_c={}
        #檢查s串，并登記s的內(nèi)容
        for i in range(len(s)):
            dict_c[s[i]]=dict_c.get(s[i],0)+1  #默認(rèn)為0
            
        #檢查t串，并清空s的內(nèi)容，如果t和s互為回文，則字典元素個(gè)數(shù)互相抵消
        for i in range(len(t)):
            dict_c[t[i]]=dict_c.get(t[i],0)-1  #默認(rèn)為0
            
        for d in dict_c:
            if dict_c[d] != 0:
                return False
        
        return True
        
        

3 算法分析

這里主要利用回文的概念，t把s的所有元素都恰好用一遍，可以通過(guò)統(tǒng)計(jì)各個(gè)元素出現(xiàn)的次數(shù)來(lái)進(jìn)行判斷。如果s和t等長(zhǎng)且是回文，則所有字符出現(xiàn)的次數(shù)是相等的。
時(shí)間復(fù)雜度為O(n)
空間復(fù)雜度為O(n)