單字接龍 用單字拼出整個句子 DP應用 Leetcode #140_Word Break II
題目敘述
題目會給定我們一個字串s，和一組單字庫wordDict。
問我們能不能透過字串串接的方式，從單字庫裡面的字拼成原本的字串s?
可以的話，返回所有拼字接龍的解答。
無解的話，返回空陣列 [ ]。
註:
題目還允許重複使用字庫裡面的字去串接。
測試範例
Example 1:
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]
Example 2:
Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []
約束條件
Constraints:
1 <= s.length <= 20
目標字串s長度介於1~20之間。
1 <= wordDict.length <= 1000
單字庫最少有一個單字，最多有1000個單字。
1 <= wordDict[i].length <= 10
每個單字長度最少一個字，最長10個字
sandwordDict[i]consist of only lowercase English letters.
題目輸入全程都只會用到小寫英文字母。
- All the strings of
wordDictare unique.
單字庫裡的單字都是相異，保證不重複。
- Input is generated in a way that the length of the answer doesn't exceed 105.
測試平台保證解答長度不會超過十萬。
觀察: 如何用單字串接?
其實這題是系列題前一題Word Break I 的延伸。
一魚n吃 用DP來進行字串拆分配對 Word Break_Leetcode #139
原本在前一題Word Break I問的是，能不能拼接成功? 是回答Yes / No的是非題。
這題Word Break II類似，改成問如何拼接，請把拼接的方法全部列出來的應用題。
演算法 DP動態規劃 + 針對單字長度做最佳化
怎麼定義DP狀態?
可以定義DP[i] 代表子字串s[i:]的單字串接方法。
那麼最終答案自然就是DP[0]，也就是s[0:] = s本身的單字串接方法。
DP遞迴關係(狀態轉移關係式)是怎麼表達?
逐步推進，假如我們找到某個prefix前綴剛好是單字庫裡的某個單字，那麼prefix加上剩下的後綴子字串串接方法就是合法的拼接方法數。
DP[i] += DP[i+length] 如果 s[i: i+length]這個前綴剛好是單字庫裡的單字。
優化的技巧
推進的時候，可以不用暴力的去try每個index，只要針對有可能的長度去做搜尋即可。
為什麼?
為因單字庫已經事先知道了，那些長度不可能的前綴，是沒有辦法被單字串接的，可以直接跳過。
遞迴什麼時候結束?
當index前進到字串s的未端，也就是len(s)的時候，代表已經用單字串接出整個字串s。
這時候後面已經式空字串沒有東西了，遞迴結束，自然停止。
OK，到這邊DP狀態定義、DP狀態轉移關係式、終止條件都釐清了。
接下來轉成具體的程式碼即可。
程式碼 DP動態規劃 + 針對單字長度做最佳化
# DP = DFS + memoization = DFS + DP table
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
# word set to speed up element membership lookup
wordBank = set(wordDict)
# set of length of words
possible_length = set( map(len,wordBank ) )
## DP table
# key: search index
# value: list of matched words in s[index:]
dp = { len(s): [ [] ]}
def match(index: int) -> List[List[str]]:
if index in dp:
return dp[index]
ans = list()
# Scan each possible split index from left to right
for length in possible_length:
# This round is skipped due to length out of boundary
if index+length > len(s):
continue
word = s[index:index+length]
if word in wordBank:
# Current word is matched
# Try to match remaining substring
parse_postfix = match(index+length)
for parsing_reulst in parse_postfix:
ans.append( [word] + parsing_reulst )
dp[index] = ans
return ans
# ------------------------------------------
return [" ".join(words) for words in match(index=0) ]
複雜度分析
令字串s的長度為n,
時間複雜度: O( n * 2^n )
最差情況下，單字庫裡的單字只有一個字母，相當於每個切割點都有展開來檢查，耗費O( 2^n )。
每次檢查需要耗費O(n)去切割前綴字串，看看是否在單字庫裡面。
空間複雜度: O( n * 2^n )
總共有O(2^n)種展開狀態
每個合法狀態最後寫入解答時，拼接總長度剛好為O(n)。
關鍵知識點
聯想到系列題的Word Break I，用到的都是同一種想法，
從左到右逐漸推進，檢查每個前綴是否能匹配單字庫裡的單字。
接著DP遞迴呼叫，檢查剩下的後綴子字串。
Reference
你可能也想看
