#242. Valid Anagram

題目描述

給你兩個字串s和t，如果t是s的同字母異序詞，回傳true，反之回傳false。
同字母異序詞是一個字或詞可以被重新排列成一個新的字或詞，通常每個字母都會使用到一次。

限制條件

1 <= s長度、t長度 <= 5*10^4
s和t由小寫字母組成。
通常每個字母都會使用到一次。

解題思路

由於s和t如果是同字母異序詞的話，那麼它們的字母的數量會相等。
那麼就可以用一個很簡單的加減法概念來作處理，如果兩邊相等的話，假設一邊為負值，另外一邊為正值，相加起來就會等於0，如果不等於0的話，則兩邊不相等。
要計算每一個字母出現次數是否相等，我們需要建立儲存字母的資料結構，這邊使用Array、List或者Hashtable都可以。

步驟：

檢查兩個字串中的每個字母，s中出現的字母按出現次數加上相對應的值，t中出現的字母案出現次數減去相對應的值。
比對儲存的每個字母出現的值，都為0則回傳true，其中一個不為0則回傳false

Hashtable

public class Solution {
	public bool IsAnagram(string s, string t) {
		//排除錯誤引數
        if(s.Length!=t.Length) return false;
        var ht = new Hashtable();
        for(int i=0;i<s.Length;i++){
            if(ht.Contains(s[i])) ht[s[i]] = (int)ht[s[i]] + 1;
            else ht.Add(s[i],1);
            if(ht.Contains(t[i])) ht[t[i]] = (int)ht[t[i]] - 1;
            else ht.Add(t[i],-1);
        }
        foreach(DictionaryEntry d in ht){
            if((int)d.Value!=0) return false;
        }
        return true;
    }
}

複雜度分析：

時間複雜度：雖然有兩個引數s和t，會花費(m+n)的時間，但是假設(m!=n)就會馬上結束，(m==n)情況才會繼續處理下去，所以實際上會花費2n的時間加上26個字母的時間，因此時間複雜度為O(n)。
空間複雜度：不論是哪個儲存字母的資料結構，最多都只會儲存26個英文字母，因此空間複雜度為O(1)。

Follow-up

如果輸入使用了Unicode字元，該如何處理呢？

回答：Unicode字元不是單一字元而是由字元編碼所組成的，舉例來說字母a在Unicode中的編碼是U+0061，十六進位表示是0x61，沒有辦法使用儲存單一型態的資料結構，因此最簡單快速的方式就是使用Hashtable來儲存Unicode的字元編碼，Hashtable可以儲存多種類型的資料型態並進行映射，因此最適合用來儲存Unicode。

學習重點

字元的操作。
HashMap的應用。
Unicode字元與字元的差別。