主題

LeetCode - 819. Most Common Word 解題心得

Not In My Back Yard | 2021-01-19 00:00:06

題目連結:


題目意譯:
給定一個段落 paragraph 以及一個列表 banned 代表禁用詞,回傳最頻繁出現的字詞其為非禁用詞之一。保證至少有一個字詞沒有被禁用,且答案唯一。

banned 中的字詞是以小寫給定且不含任何標點符號。paragraph 中的字詞不區分大小寫。此外,答案應為小寫。

注:
1 ≦ paragraph.length ≦ 1000.
0 ≦ banned.length ≦ 100.
1 ≦ banned[i].length ≦ 10.
答案是唯一的,且為小寫形式(即使其於 paragrapgh 中出現可能含有大寫之形式或就算其是作為專有名詞出現都算作一次的出現)
paragraph 只由字母、空白或是標點符號 !?',;. 所組成。
不存在任何連接號或是由連接號組成的組合字詞。
字詞只由字母組成,絕不會有引號或其他標點符號出現。



範例測資:
輸入:paragraph = "Bob hit a ball, the hit BALL flew far after it was hit." 、 banned = ["hit"]
輸出: "ball"
解釋:
"hit" 出現三次,但是其為一個禁用詞。"ball" 出現兩次(且沒有其他詞如此),所以其為最頻繁非禁用詞於 paragraph 中。注意 paragraph 中的字詞不區分大小寫,其中標點符號將被忽略(即便相鄰於任何字詞,例如 "ball,"),且 "hit" 不算作答案即使出現較多次因其為禁用詞。


解題思維:
使用雜湊表(Hash Table)先將 banned 裡的字詞放進去方便搜尋。接著用另一個雜湊表儲存 paragraph 裡的字詞的出現次數,但是統計的同時記得先判斷是否為禁用詞。

統計完所有字詞後,再掃過一次統計用的雜湊表去找出出現最多次的字詞,該詞即 為所求。




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

創作回應

更多創作