前往
大廳
主題

LeetCode - 2452. Words Within Two Edits of Dictionary 解題心得

Not In My Back Yard | 2023-09-23 12:00:37 | 巴幣 0 | 人氣 85

題目連結:


題目意譯:
你被給定兩字串陣列 queries 和 dictionary。每個陣列中所有字詞都由小寫字母組成且都有著相同的長度。

在一次編輯之中,你可以從 queries 中選擇出一個字詞,並將任意一個字母變成任意字母。請從 queries 中找出所有字詞,在各自經過最多兩次編輯後,等於 dictionary 中的某個字。

回傳由 queries 中所有的字詞滿足,滿足經過最多兩次編輯後等於 dictionary 中的某個字。請以這些字詞在 queries 中出現的順序來回傳這些字詞。

限制:
1 ≦ queries.length, dictionary.length ≦ 100
n == queries[i].length == dictionary[j].length
1 ≦ n ≦ 100
所有 queries[i] 和 dictionary[j] 都由小寫英文字母組成。



範例測資:
範例 1:
輸入: queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
輸出: ["word","note","wood"]
解釋:
- 將 "word" 中 'r' 變成 'o',讓它可以等於 dictionary 中的 "wood"。
- 將 "note" 中的 'n' 變成 'j' 以及讓 't' 變成 'k',令其變成 "joke"。
- "ants" 需要多於兩次的編輯來變成 dictionary 中的字詞。
- "wood" 可以保持不變(0 次編輯)來對應到 dictionary 中的字。
因此,我們回傳 ["word","note","wood"]。

範例 2:
輸入: queries = ["yes"], dictionary = ["not"]
輸出: []
解釋:
兩次編輯無法使 "yes" 變成與 "not" 相等。因此我們回傳一個空陣列。


解題思維:
直接掃過 queries 中每個字詞 queries[i],對於每個字詞掃過 dictionary 中每個字 dictionary[j],然後每個字母對齊(註:兩者長度保證相同)並比較不同之處。如果不同之處之數量 ≦ 2,則代表我們可以在兩次編輯內將 queries[i] 變成 dictionary[j]。

然後把上述中找出來的 queries[i] 依照順序放到一個列表中回傳即可。




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

創作回應

更多創作