一魚n吃 用DP來進行字串拆分配對 Word Break_Leetcode #139
題目敘述
題目會給定我們一個字串s，和一組字庫wordDict。
問我們能不能透過字串串接的方式，從字庫裡面的字拼成原本的字串s?
可以的話，返回True。
無解的話，返回False。
註:
題目還允許重複使用字庫裡面的字去串接。
測試範例
Example 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
leet 和 code 串接 可以拼出leetcode
Example 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
apple, pen, apple 串接，可以拼出 applepenapple
題目允許重複使用字庫裡面的字去串接。
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
無解，返回False
約束條件
Constraints:
1 <= s.length <= 300
輸入字串s的長度介於1~300之間。
1 <= wordDict.length <= 1000
字庫裡面的單字數量介於1~1000之間。
1 <= wordDict[i].length <= 20
字庫裡的每個單字的長度介於1~20之間。
sandwordDict[i]consist of only lowercase English letters.
字串s和字庫裡的單字都只會有小寫英文字母。
- All the strings of
wordDictare unique.
字庫裡的單字不會重複。
演算法
不只一種解法，我們這邊使用DP動態規劃作為示範。
Dynamic programming的解題框架
再次複習Dynamic programming的解題框架，可分為三大步驟
1.定義狀態 [我在哪裡]
2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]
1. 定義狀態 [我在哪裡]
DP狀態的定義一開始其實題目沒給，但是沒關係，我們可以試著先定義、推導看看。
不妨就定義
DP[i] = 從 index i 開始的子字串S[i:] ，能不能從字庫裡的單字串接拼出來?
= True 如果可以 / False 如果無解
那麼，根據定義，最終我們想知道的就是整個字串S[0:]也就是字串s本身，能不能從字庫裡的單字串接拼出來?
DP[ i = 0 ] 就是我們最終要回傳的答案，型別為Boolean值，
True代表有解 / False代表無解。
2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
題目已經講是從字庫裡面的單字去做串接。
那麼，我們可以掃描過每個可能的切割點j，看看切割出來的S[i:j]是不是字庫裡面的單字?
假如是，那麼S[i:j]可以對應到字庫裡面的單字，接著，下一步就去試著配對S[j:]之後的子字串，相當於程式碼裡面的DP function呼叫 match( j )。
假如不是，那麼S[i:j]無法對應到字庫裡面的單字，這回合的配對不成功，直接往右移動一格，跳到下一輪切割點j+1的檢查。
image.png
3. 釐清初始狀態(終止條件) [第一步怎麼走，怎麼出發的]
什麼時候檢查一定會停下來?
當所有可能的切割點都檢查完了，已經移動到最後面，
這時候index i = len(s) = 恰好等於輸入字串的長度。
s[ len(s): ] = "" = 相當於空字串
空字串一定可以拼的出來，就是什麼單字都不選擇就可以造出空字串。
所以，終止條件就是DP[ len(s) ] = True 作為初始化Initialization的動作。
接下來，把剛才完成的三步驟寫成對應的程式碼，這邊以python作為示範
程式碼
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordBank = set(wordDict)
dp = defaultdict(lambda:False)
# Define DP[i] = S[i:] can be made by selecting word in wordBank
# Base case initialization
# Empty string can be made by selecting nothing = ""
dp[len(s)] = True
def match(i):
# Look-up DP table
if i in dp:
return dp[i]
# Scan each possible split index from left to right
for j in range(i+1, len(s)+1):
if s[i:j] in wordBank and match(j):
# s[i:j] can match a word in wordBank
# Try to match remaing string s[j:]
dp[i] = True
return True
# All matching process on each split index failed
dp[i] = False
return False
# ------------------------
return match(i=0)
複雜度分析
令字串s的長度為n, 字庫的長度為W
時間複雜度:
O( n^2 + W )
掃描切割點從0滑動到尾端len(s)，所需時間為O(n)
切割每個子字串s[i:j]又耗費O(n)
額外在開頭的地方需要建立wordBank集合，耗費O(W)
總共所需時間為O(n^2 + W)
空間複雜度:
遞迴深度從i=0 遞迴到 i = len(s)，所需stack深度為O(n)
每次遞迴的過程中，需要切割每個子字串s[i:j]又耗費O(n)
額外在開頭的地方需要建立wordBank集合，耗費O(W)
總共所需空間為O(n^2 + W)
關鍵知識點
題目已經講是從字庫裡面的單字去做串接。
那麼，我們可以掃描過每個可能的切割點j，看看切割出來的S[i:j]是不是字庫裡面的單字?
假如是，那麼S[i:j]可以對應到字庫裡面的單字，接著，下一步就去試著配對S[j:]之後的子字串，相當於程式碼裡面的DP function呼叫 match( j )。
假如不是，那麼S[i:j]無法對應到字庫裡面的單字，這回合的配對不成功，直接往右移動一格，跳到下一輪切割點j+1的檢查。
Reference:
