前往
大廳
主題

LeetCode - 748. Shortest Completing Word 解題心得

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

題目連結:


題目意譯:
給定一字串 licensePlate 以及一個字串陣列 words,找到 words 中最短的完成字詞。

一個完成字詞為一字詞,其包含 licensePlate 中的所有字母。請忽略 licensePlate 中的數字以及空白,且將大小寫字母視為一致。如果字母在 licensePlate 中出現不只一次,則字詞應含有相對等數量的該字母。

例如,如果 licensePlate = "aBc 12c",則其包含字母 'a' 、 'b' (忽略大小寫)以及兩個的 'c'。

回傳 words 中最短的完成字詞。保證答案存在。如果有多個最短的字詞,則回傳第一個出現於 words 中的。

限制:
1 ≦ licensePlate.length ≦ 7
licensePlate 包含數字、字母(大寫或是小寫)以及空白 ' '。
1 ≦ words.length ≦ 1000
1 ≦ words[i].length ≦ 15
words[i] 由小寫英文字母組成。



範例測資:
範例 1:
輸入: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
輸出: "steps"
解釋: licensePlate 包含字母 's' 、 'p' 、 's' (忽略大小寫) 以及 't'。
"step" 包含 't' 以及 'p',但只包含一個 's'。
"steps" 包含 't' 、 'p' 以及兩個 's' 字元。
"stripe" 少了一個 's' 。
"stepple" 少了一個 's' 。
由於 "steps" 是唯一一個包含所有字母的字詞,所以其為答案。

範例 2:
輸入: licensePlate = "1s3 456", words = ["looks","pest","stew","show"]
輸出: "pest"
解釋: licensePlate 只包含字母 's'。所有字詞皆包含 's',但其中 "pest" 、 "stew" 、 和 "show" 為最短的。答案為 "pest",因為其為三個最短字詞中最早出現的。

範例 3:
輸入: licensePlate = "Ah71752", words = ["suggest","letter","of","husband","easy","education","drug","prevent","writer","old"]
輸出: "husband"

範例 4:
輸入: licensePlate = "OgEu755", words = ["enough","these","play","wide","wonder","box","arrive","money","tax","thus"]
輸出: "enough"

範例 5:
輸入: licensePlate = "iMSlpe4", words = ["claim","consumer","student","camera","public","never","wonder","simple","thought","use"]
輸出: "simple"


解題思維:
先將 licensePlate 中的字母過濾出來並且統一轉成小寫。接著掃過 words 中的所有字詞,對於每個字詞統計其字母之出現次數,看有無包含到 licensePlate 中所有字母。

如果有,則將其跟答案的候補(一開始候補為一個很長的字串,長於所有可能的字串)作長度的比較,如果現在這個字串較短就將該字串選為新的候補。如果較長或是長度一樣則忽略。掃過所有字詞後,候補的內容即是所求。




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

創作回應

更多創作