拼字遊戲 拼出最高分的單字組合 (DFS回溯法應用) Leetcode #1255

小松鼠
發佈於演算法專欄 個房間
閱讀時間約 12 分鐘

題目敘述

輸入會給定一組限量供應的英文字母、每個英文字母對應的分數單字庫

要求我們從給定的英文字母去拚出單字庫中的單字,盡可能地拼出最高分的單字組合

請問最高分數是多少?

每個單字最多只能用一次,不可以重複使用


題目的原文敘述


測試範例

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+回溯法框架_理解背後的本質


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

[1] Maximum Score Words Formed by Letters - LeetCode

52會員
337內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!