拼字遊戲 拼出最高分的單字組合 (DFS回溯法應用) Leetcode #1255
題目敘述
輸入會給定一組限量供應的英文字母、每個英文字母對應的分數、單字庫。
要求我們從給定的英文字母去拚出單字庫中的單字，盡可能地拼出最高分的單字組合。
請問最高分數是多少?
每個單字最多只能用一次，不可以重複使用。
測試範例
Example 1:
Input: 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]
Output: 23
Explanation:
Score a=1, c=9, d=5, g=3, o=2
Given letters, we can form the words "dad" (5+1+5) and "good" (3+2+2+5) with a score of 23.
Words "dad" and "dog" only get a score of 21.
Example 2:
Input: 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]
Output: 27
Explanation:
Score a=4, b=4, c=4, x=5, z=10
Given letters, we can form the words "ax" (4+5), "bx" (4+5) and "cx" (4+5) with a score of 27.
Word "xxxz" only get a score of 25.
Example 3:
Input: 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]
Output: 0
Explanation:
Letter "e" can only be used once.
約束條件
Constraints:
1 <= words.length <= 14
單字庫words裡最少一個單字，最多14個單字
1 <= words[i].length <= 15
每個單字words[i]的長度最少一個字母，最長15個字母。
1 <= letters.length <= 100
letters最少提供一個英文字母，最多提供100個會重複的英文字母。
letters[i].length == 1
letters提供的都是長度為1的英文字母。
score.length == 26
分數陣列score裡面儲存的整數分別代表a~z每個字母對應的分數。
0 <= score[i] <= 10
每個字母分數最低0分，最高10分
words[i],letters[i]contains only lower case English letters.
題目用到的都只會是小寫英文字母。
觀察
基本上有兩種思路，
第一種是挑限量的英文字母去拼單字，看最高能拚幾分?
第二種是挑單字去消耗提供的英文字母，看最高能湊出幾分?
第二種比較好，為什麼?
從題目敘述和約束條件可以知道
英文字母最多可能會供應100個有重複的英文字母；
但是，單字庫裡最多也才14個單字。
同樣是展開，從單字庫裡去展開，分支情況就會少非常多；
而且，我們還可以用剪枝Pruning的技巧，排除掉那些不可能產生最高分樹的組合。
演算法 DFS + 回溯法 + 剪枝優化
比較敏銳的同學，應該已經選到用DFS+回溯法去列舉所有可能的單字組合情況，去找出擁有最高分數的單字組合。
不免俗，這邊再幫讀者快速複習一次，鞏固知識點。
(還沒看過的讀者，可以看這篇文章來學習這種對於枚舉類的場景很實用的演算法架構)
DFS + 回溯法 演算法框架
用途:
展開所有可能的路徑(或者說狀態)，並且把符合條件的狀態加入到最終的結果。
def backtrack( parameter ):
# 終止條件
if stop condition:
save result if needed # 有需要的話，儲存當下的狀態作為結果
return
# 通則
for each possible next selection
make a selection # 做出一個選擇
backtrack( updated patameter ) # 遞回展開下一層
undo selection # 撤銷選擇，回到原始狀態，準備做下一個選擇
return
在這題枚舉對像是什麼?
枚舉單字庫裡的每個單字。
所以start index從0開始拜訪到最後一個。
怎樣叫做合法的單字枚舉?
當供應的字典dictionary 還足夠拼出當下這個單字words[i]時
(對應需要的字母數量紀錄在cur_spell )，就是合法的枚舉。
如何更新最大分數?
每次拚出一個單字時，就加入對應的分數 word_score[i]，
每層遞迴都隨時更新分數的最大值。
什麼時候遞迴終止?
當供應的字典dictionary一直被消耗，已經無法拼出任何一個單字庫中的單字時，
遞迴終止，自然結束。
剪枝的優化策略是?
每層遞迴會檢查，如果剩下的單字分數加起來(假設的最好情況) 還比目前已知的分數最大值還小，那麼可以提早結束這條搜索路徑，因為不可能產生更好的結果。
OK，到這邊已經釐清遞迴參數、遞迴通則、終止條件、還有剪枝的優化策略。
接下來轉成對應的程式碼即可。
程式碼 DFS + 回溯法 + 剪枝優化
class Solution():
def maxScoreWords(self, words, letters, score):
# key: word
# value: total score for specific word
word_score = [ sum(score[ord(char)-ord('a')] for char in word) for word in words]
# key: word
# value: character needed to spell specific word
word_spell = [ Counter(word) for word in words ]
# Initial letters we have in input array: letters
offering = Counter(letters)
# Try to pick word as many as possible to reach highest score
def pickWord( start, points, dictionary ):
# Early stop those branches which cannot yield better score
if points + sum(word_score[start: ]) < pickWord.max_score :
return
# Update highest score during enumeration in DFS
pickWord.max_score = max(pickWord.max_score, points)
# Pick a word which we can spell, then adding score
for i, cur_spell in enumerate(word_spell[start:], start):
# Check we still have enough letters to spell current word
if all( cur_spell[char] <= dictionary[char] for char in cur_spell):
pickWord( i+1, points+ word_score[i], dictionary - cur_spell )
return
#------------------------------
# Since this is a maximal value optimization, we initialize to relative low value 0
pickWord.max_score = 0
# Start picking words from first word to last word
pickWord( start=0, points=0, dictionary=offering )
# Final best result = maximal score
return pickWord.max_score
複雜度分析
令
w = letter陣列的長度。
n = words單字庫陣列的長度 = 單字總數。
s = 單字庫裡單字的平均長度。
時間複雜度 O(w+ns+s * 2^n ) ~ O( s *2^n )
建造供應字母的字典、分數表格、每個單字的字母表格耗費O(w+ns)
DFS遞迴耗費O(s * 2^n)
每個單字選或不選，總共有2^n總情況，每個情況需要耗費O(s)去檢查是否還能用字典剩餘的英文字母拼出來。
空間複雜度 O(n)
建造分數表格、每個單字的字母表格需耗費空間O(n)
DFS遞迴 run-time call stack depth也是O(n)
關鍵知識點
遇到枚舉類的應用場警，記得聯想到很實用的DFS+回溯法演算法框架合縱連橫: DFS+回溯法框架_理解背後的本質。
枚舉時，記得先思考一下，從哪個對象開始枚舉，分支情況會比較少，比較少的那個代表run-time所需時間也比較短，效率更好。
Reference
