從LeetCode學演算法 - 41 Hash Table (2)

0242. Valid Anagram (Easy)

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

1
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?

給定兩個字串s跟t，
寫出一個函式來判斷t是否是a的一個anagram(易位構詞)。

所謂的anagram就是指將這個字串的字母搬動順序以後，
可以組成另一個字串的遊戲，這在很多推理小說裡都有出現過，
比如達文西密碼或者哈利波特XD

那麼，怎麼確切知道s跟t是否是彼此的anagram呢？
我們比較幸運只需要檢查正確與否就好，所以一般常見的解法有幾個：

排序(暴力?)法
既然完全是由相同的字母及相同使用字母的個數組成，
那就代表只要將兩個字串進行排序，最後它們會長得一模一樣 。
但這樣作的時間複雜度為O(n log n)(n為字串長) 。
雖然能夠通過測試，但似乎不是很理想。
Hash Table 法
上次我們已經介紹過了Hash Table的概念，那麼這次我們應該也可以使用相同的方式來處理。由於題目已經告知字串僅含小寫字母，也就是a-z，
只要依序掃瞄過兩個字串，將字串所含每個字母的個數計算是否相等，
即可判定結果。
這麼作只需要O(n) 的時間複雜度，空間部分只需要O(1) 。
(因為是26個字母 ，所以陣列長是固定的)

我們可以利用上一次提到的ASCII的方式，
來對a-z 的部分位移到一個計數陣列的0到25 ，
同時，掃過s 的時候將對應的字母計數遞增 ，
掃過t 時將對應的字母計數遞減 ；
一旦有字母是遞減到小於零 的話就可以直接判定s和t彼此並非anagram。

Java的版本完整演示了上述的流程。

Python的部分這邊也可以另外使用別的方法，
這邊提供幾個比較簡便且複雜度一樣的方法：

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(n)/O(1))

「如果大小寫視為相同？」
(使用類似Java的方式，但每個字元要先確認是否是大寫，
若是，先將其轉為小寫才往陣列中存放，之後的做法應該是一致的。)
(ASCII中A-Z是65~~90而a-z是97~~122，可以先平移對應的相差量)

「如果還有其他英文字母以外的字元？」
(將陣列改成用HashMap，
key存放字元，value存放出現次數。Python則用Dict即可)

「如果大小寫視為相同，空格及標點符號要省略呢？
(沒錯，就跟達文西密碼的留法一樣，沒人在管標點的XD)」
(可以嘗試刪去不需要的，或只取英文字母的部分。)

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~