主題

LeetCode - 804. Unique Morse Code Words 解題心得

Not In My Back Yard | 2021-01-15 00:00:06 | 巴幣 0 | 人氣 44

題目連結:


題目意譯:
國際摩斯電碼(International Morse Code)定義一個標準加密法,其中每個字母分別映射到一串點(Dot)以及劃(Dash),如以下: 'a' 映射到 ".-" 、 'b' 映射到 "-..." 、 'c' 映射到 "-.-.",以此類推。

為了方便起見,26 個英文字母之完整對應表格如下:
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

現在給定一個字詞列表 words,每個字詞 word 可以寫為其每個字母的對應摩斯電碼之串接。例如,"cab" 可以寫作 "-.-..--..."(其為 "-.-." + ".-" + "-..." 之串接)。 我們定義此種串接為一個字詞的變換。

回傳 words 中有多少種相異的變換。

注:
words 長度最長為 100。
每個 words[i] 之長度介於 [1, 12] 之間。
words[i] 只由小寫字母組成。



範例測資:
輸入: words = ["gin", "zen", "gig", "msg"]
輸出: 2
解釋:
每個字詞的變換為:
"gin" → "--...-."
"zen" → "--...-."
"gig" → "--...--."
"msg" → "--...--."
其中有兩種不同的變換,分別為 "--...-." 以及 "--...--." 。


解題思維:
利用雜湊表(Hash Table)去儲存有多少種相異的變換結果。

接著就是模擬即可——掃過 words 中每個字詞,對於每個字詞中每個字母轉成對應的摩斯電碼,然後將這些摩斯電碼連接起來即是該字詞的變換,接著將這些變換都丟進雜湊表裡。

最後雜湊表的大小即是所求。




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

創作回應

更多創作