前往
大廳
主題

LeetCode - 1255. Maximum Score Words Formed by Letters 解題心得

Not In My Back Yard | 2023-10-20 12:00:22 | 巴幣 0 | 人氣 68

題目連結:


題目意譯:
給定一個字詞列表 words、一個單一字母列表(可能有重複)letters 以及每種字母的分數 score。

回傳任一合法字詞集合的最大分數,其中每個集合中的字詞可以被給定的字母組成(words[i] 不得被選定兩次或以上)。

不一定要使用掉 letters 中的所有字元,而每個字母只能被使用一次。而每一種字母的分數 'a' 、 'b' 、 'c' 、 …… 、 'z' 依序給定於 score[0] 、 score[1] 、 score[2] 、 …… 、 score[25]。

限制:
1 ≦ words.length ≦ 14
1 ≦ words[i].length ≦ 15
1 ≦ letters.length ≦ 100
letters[i].length == 1
score.length == 26
0 ≦ score[i] ≦ 10
words[i] 和 letters[i] 只由小寫英文字母組成。



範例測資:
範例 1:
輸入: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
輸出: 23
解釋:
分數  a=1 、 c=9 、 d=5 、 g=3 、 o=2
給定 letters,我們可以組成字詞 "dad"(5+1+5)以及 "good"(3+2+2+5),其分數值為 23。
字詞 "dad" 加上 "dog" 只會得到 21 分。

範例 2:
輸入: words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
輸出: 27
解釋:
分數  a=4 、 b=4 、 c=4 、 x=5 、 z=10
給定 letters,我們可以組成字詞 "ax"(4+5)、 "bx"(4+5) 以及 "cx"(4+5),其分數值為 27。
字詞 "xxxz" 只會得到 25 分。

範例 3:
輸入: words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
輸出: 0
解釋:
字母 "e" 只能被使用一次。


解題思維:
直接窮舉所有可能的字詞組合,即 2 ^ m 種,其中 m 為 words 的長度。然後對每一種檢查字母使用情況有沒有在允許範圍內(即 letters 允許的使用數量限制)。然後把那些合法的組合,計算它們的分數值取最大值即為所求。




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

創作回應

更多創作