切換
舊版
前往
大廳
主題

LeetCode - 242. Valid Anagram 解題心得

Not In My Back Yard | 2020-09-22 22:49:57 | 巴幣 4 | 人氣 133

題目連結:


題目意譯:
給定兩字串 s 和 t ,撰寫一個函式去判斷 t 是否 s 的一組易位構詞(Anagram)。

注:
你可以假設字串只含有小寫字母。

進階:
如果輸入含有 Unicode 字元的話呢?你要怎麼調整你的程式去處理該種情況?



範例測資:
範例 1:
輸入: s = "anagram", t = "nagaram"
輸出: true

範例 2:
輸入: s = "rat", t = "car"
輸出: false


解題思維:
先判斷 s 的長度是否與 t 相同,因為如果長度都不相同了,那 t 一定不會是 s 的易位構詞。

接著用一個陣列統計每個英文字母的出現次數。當掃過 s 的字元時,出現什麼字元就將該字元的次數 + 1 ;當掃過 t 的字元時,就將該字元的次數 - 1。

最後再掃過一次陣列,看有沒有字元的出現次數不是 0 。如果有不是 0 的,則代表 s 與 t 互不為易位構詞;反之,皆為 0 的話,兩者才是互為易位構詞。



那如果有 Unicode 字元呢?將上列的陣列換成雜湊表,並將輸入的字串之型態改為 wstring (如果是 C++ 的話,這樣就可以支援 Unicode 字元),而此時裡字串的每個字元型態為 wchar 。然後依照上面的策略將每個丟進去,最後再判斷即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作