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

Natalia Y. on Unsplash

題目敘述

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

請問最高分數是多少?

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

題目的原文敘述

測試範例

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