題目連結:
題目意譯:
你被給定兩字串陣列 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] 依照順序放到一個列表中回傳即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。