前往
大廳
主題

LeetCode - 49. Group Anagrams 解題心得

Not In My Back Yard | 2021-09-12 00:00:03 | 巴幣 0 | 人氣 107

題目連結:


題目意譯:
給定一字串陣列 strs ,將易位構詞(Anagram)之字詞分類在一起。你可以按照任意順序回傳答案。

一個易位構詞為一單字或片語由重新排列另一個單字或片語而形成,且通常是使用掉原本的全部字母且僅使用恰好一次。

限制:
1 ≦ strs.length ≦ 10 ^ 4
0 ≦ strs[i].length ≦ 100
strs[i] 由小寫英文字母組成。



範例測資:
範例 1:
輸入: strs = ["eat","tea","tan","ate","nat","bat"]
輸出: [["bat"],["nat","tan"],["ate","eat","tea"]]

範例 2:
輸入: strs = [""]
輸出: [[""]]

範例 3:
輸入: strs = ["a"]
輸出: [["a"]]


解題思維:
將每個字串的字元按照字典序由小排到大,然後利用雜湊表(Hash Table)將排序後的字串作為鍵值。因此如果兩個字串的鍵值一樣則代表兩者互為易位構詞。

因此最後掃過雜湊表,對於每個鍵值裡有的原始字串包成一個列表(List),然後再將這些列表包成一個列表即是所求。




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

創作回應

更多創作