主題

ZeroJudge - a541: 字典 解題心得

Not In My Back Yard | 2021-02-17 00:00:08 | 巴幣 2 | 人氣 37

題目連結:


題目大意:
輸入第一列給定一正整數 N (1 < N < 70000),代表有駿原先記得的單字數量。接著有 N 列輸入,每列給定一個字串(只由小寫英文字母組成,且長度 ≦ 20),代表有駿記得的單字內容。

輸入第 N + 2 列給定一正整數 Q (1 < Q < 70000),代表 Q 筆單字詢問。接著有 Q 列輸入,每列給定一個字串(同樣只由小寫英文字母組成,且長度 ≦ 20),代表詢問有駿記不記得該單字。如果記得請輸出「yes」;反之,請輸出「no」,且有駿會將其記住(下次再詢問則會記得)。



範例輸入:
4
henry
john
mary
cindy
5
andy
cindy
vicky
leo
leo


範例輸出:
no
yes
no
no
yes


解題思維:
先將有駿記得的 N 個單字放進雜湊表(Hash Table,例如 C++ 的 unordered_set 或是 Python 的 dict)裡儲存,然後對於每筆詢問去查表。有出現在表裡,則代表記得,輸出「yes」;反之,則不記得,因此輸出「no」並且將該單字放進雜湊表裡。




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

創作回應

更多創作