拼字遊戲 拼出最高分的單字組合 (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會員
339內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
你可能也想看
雀巢可可脆片 新品"字母趣" 用麥片拼字雀巢 可可脆片字母趣 他除了可可外還有加入魚油DHA
Thumbnail
avatar
小玉西瓜沒有籽
2023-05-04
【Spell me Out - 拼出我心】優視頻道 UChannel TV 周五晚,在矽谷具有歷史的 FOX Theater, 優視原創紀錄片系列有場首映會,是近來獲獎連連,女主角是王樂怡,曾有亞洲私募女王之稱。她在卅多歲時,在香港會議中倒地,中風使得她全身癱瘓,只能靠眨眼來拼出字母表達她的言語。其父是台灣知名創投界大老、前#全球玉山科協理
Thumbnail
avatar
喬琚@矽谷
2022-11-13
解析:這些方塊是什麼?最近流行什麼?拼字遊戲 Wordle 居然也有注音跟倉頡版為什麼大家每天都要分享一篇灰色、黃色、綠色格子的圖片?這些方塊圖是一款跟「字」有關的小遊戲「Wordle」,而網友們分享的圖片代表他們玩遊戲的結果,是用了幾次機會才答對! 自然輸入法 也是跟「文字」有關的服務,今天跟大家介紹的小遊戲「Wordle」也是跟「文字」相關! Wordle 玩法說明:
Thumbnail
avatar
GPT工作術|與你一起補給工作的AI能量 智慧寫作·聲音創造·法遵合規
2022-02-09
《拼出一個夢》拼音比賽和民族《拼出一個夢》是一部描述關於盛行美國的兒童拼字遊戲,在這裡很多人會把拼字跟印度裔劃為等號,為什麼?因為幾乎印度裔容納多屆拼字遊戲的冠軍與前半部的名次,這讓印度裔在美國以得獎和才能被人所見,但面對背誦出一個又一個艱深困難甚至字典都難有的詞彙,得獎的背後必須有多少的努力。
Thumbnail
avatar
陸坡 (LUPO)
2021-06-10
拼字還能這樣玩-TYPOMAN去年夏天我意外發現了這款遊戲。它將英文的拼字解謎與動作冒險做結合,創造出一種非常獨特的遊戲機制。再加上畫面表現乾淨俐落卻又不失藝術美感,除了「遊戲性」與「美術性」之外,其實「故事劇情」的驚奇度也是相當出色。 本文也會主要以這三點出發做探討,一起來看看這款有趣的「拼字解謎」「動作冒險」遊戲吧!
Thumbnail
avatar
莊凱翔
2019-03-11
【怎麼拼出一個展?】詩宅之眼看書展:現代詩的無限可能<p>如果要選擇一種文類當做「獨立出版」的指標,「詩」或許最為適合。不論在什麼樣的場合,最不按牌理出牌的總是詩人跟他們的作品。特別在國際書展這種百花齊放的戰場,簡直是為詩人們準備的華麗舞台。詩集出版發展有其歷史脈絡,若只懂得看熱鬧不免有點可惜。本次「怎麼拼出一個展」系列專題的最後一篇就請身兼詩人、動漫愛好者及詩集收藏家於一身的林群盛,分享他充滿國際觀的宅知識及潛藏於每一首詩、每一本書的無限可能。</p>
Thumbnail
avatar
重讀者
2016-04-01
【怎麼拼出一個展?】寫作本身,就是一場驚喜不斷的旅程──專訪妙麗葉‧芭貝里<p>《刺蝟的優雅》全球銷售突破 600 萬本,一舉打開了芭貝里在全球文壇的知名度,之後的整整八年,她沒再出版其他作品,也少有新聞,甚至在 Google 搜尋框裡鍵入她的名字,跳出來的結果也都是在 2010 年前的動態。直到 2014 年,芭貝里出版了第三本作品《精靈少女》,她才又回到與世界溝通的頻道裡,然而,留下的卻是更多的驚訝與疑問……。</p>
Thumbnail
avatar
重讀者
2016-03-11
【怎麼拼出一個展?】盛況空前,白先勇大戰張愛玲?!──白先勇導讀《紅樓夢》<p>「紅學」研究裡有不少人主張《紅樓夢》後四十回是高鶚續寫,把小說寫壞了,胡適、張愛玲即是對這四十回抱持負評的代表人物,但白先勇卻非常肯定後面四十回的藝術成就,因而無法認同這些名家質疑後面四十回是高鶚續寫。</p>
Thumbnail
avatar
重讀者
2016-03-07
【怎麼拼出一個展?】辛辣、機智,而且是個只讀電子書的重度貓奴!──專訪「獵魔士」作者安傑‧薩普科夫斯基<p>「故事是整體的,人物、場景、世界觀都一樣重要。」安傑認為角色、劇情都是「故事的一部份」,所有的安排都因「故事需求」而發生。「我認識一個作家,寫到傷心處就會痛哭流涕,但我絕不會如此,我寫就是寫,不會有情緒反應,一切都是技術性的考量。我為讀者而寫,想著怎麼樣才會好看,如何吸引讀者,讀者可能看了痛哭流涕,但對我來講這沒什麼。」</p>
Thumbnail
avatar
重讀者
2016-03-07
【怎麼拼出一個展?】「拿寫作來打發時間」──專訪艾加‧凱磊<p>艾加‧凱磊似乎能夠源源不絕地創作出短篇與極短篇,對於有志嘗試創作的人,凱磊提出了幾個建議:「首先,不要一直想寫經典作品,那只會讓你想什麼都寫不出來。不要把寫作想得太重要,把它當成日常的一部分,天天做,甚至拿它來打發時間;挑對自己而言重要、有趣的主題來寫。」</p>
Thumbnail
avatar
重讀者
2016-02-25