Eisen 筆記

#139. Word Break

題目描述

給你一個字串s和一個字串字典wordDict，如果字串能夠被拆成字典中的單字，回傳true，反之則回傳false。

注意同樣的單字在字典中可能會被重複使用多次。

限制條件

  1. 1 <= s.length <= 300
  2. 1 <= wordDict.length <= 1000
  3. 1 <= wordDict[i].length <= 20
  4. s和wordDict[i]由小寫字母組成。
  5. wordDict中的單字都是唯一的。

解題思路

最直覺的作法，我們會先從s[0]開始比對wordDict中的字，如果比對成功則從s[0 + word.Length]繼續，直到i + word.Length == s.Length也就是字串的結尾，這樣就可以解決問題了。

但這邊會遇上一個問題，萬一wordDict中的字和s中的字相符，但是長度不對，導致後面的字無法被拆解，就需要全部重來。

舉例來說：
s = "leetcode"
wordDict = ["leetco","leet","code"]

"leetco"雖然可以由s拆解而成，但是拆解成"leet"、"code"才能完成題目要求。
因此我們需要對字典中的每個單字的比對結果進行記憶，才能確保找到正確的拆解組合。

Dynamic Programming

Buttom-Up

使用DP的策略，可以幫助我們記住上一次的結果，並利用上一次的結果判斷這一次的結果是否能滿足要求。

我們假設DP(0)是字串的起點，而DP(s.Length + 1)是字串的終點，wordDict中的單字如果能組成s，則終點的結果會和起點一樣。

舉例來說：
s = "leetcode"
wordDict = ["leet","code"]

起點DP(0)=true，代表我們會從起點開始，接著我們知道"leet"可以滿足s的前面4個字，而"leet"的結尾會落在DP(4)的位置，因此DP(4) = DP(4 - "leet".Length) = DP(0)。
接下來"code"同樣可以滿足從DP(4)開始的字串，而結尾會落在DP(8)，因此DP(8) = DP(8 - "code".Length) = DP(4)。
將這三個位置串接起來就會是DP(8) = DP(4) = DP(0) = true，也就是只要能滿足最初的結果，就可以達成最後的結果，也是DP概念中的根據上次的結果做出這次的決策。

換個例子來說：
s = "leetcode"
wordDict = ["ee","tco","ode"]

"ee" = DP(3) = DP(3 - "ee".Length) = DP(1)
"tco" = DP(6) = DP(6 - "tco".Length) = DP(3)
"ode" = DP(7) = DP(7 - "ode".Length) = DP(4)

可以看到DP(1)的位置沒有任何單字可以滿足，因此為false，所以從這個結果衍伸出去的DP(3)、DP(6)都因此而得到false的結果，DP(4)也是同樣的概念。

表格化後的DP結果如下：

DP("leetcode")012345678
T
"leet"TFFFDP(0)
"code"DP(0)FFFDP(4)
結果TFFFTFFFT

程式碼如下:

public class Solution {
    public bool WordBreak(string s, IList<string> wordDict) {
        var dp = new bool[s.Length + 1];
        dp[0] = true;
        for(int i=0;i<dp.Length;i++){
            foreach(var word in wordDict){
                if( i-word.Length < 0) continue;
                bool hasWord = true;
                for(int p=0;p<word.Length;p++){
                    if(s[i- word.Length +p]!=word[p]){
                        hasWord = false;
                        break;
                    }
                }                
                if(hasWord) dp[i] = dp[i - word.Length];                
                if(dp[i]) break;
            }
        }
        return dp[s.Length];
    }
}

Top-Down

Bottom-Up是從起點開始向往結果推導，Top-Down則是相反，從結果開始往回推。

DP(s.Length)是完成要求的結果True，那麼往回推導後的起點DP(0)也要等於True才能代表字串s是可以拆解成wordDict中的單字的。

public class Solution {    
    public bool WordBreak(string s, IList<string> wordDict) {
        var dp = new bool[s.Length + 1];
        dp[s.Length] = true;
        for(int i=s.Length-1;i>-1;i--){
            foreach(var word in wordDict){
                if( i+word.Length <= s.Length ){
                    bool hasWord = true;
                    for(int p=0;p<word.Length;p++){
                        if(s[i+p] != word[p]){
                            hasWord = false;
                            break;
                        }
                    }
                    if(hasWord) dp[i] = dp[ i+word.Length ];
                    if(dp[i]) break;
                }                
            }
        }
        return dp[0];
    }    
}

複雜度分析：

  • 時間複雜度：每一步都要計算結果，因此會花上n * m * k的時間，n為s.Length，m為wordDict.Length，k為wordDict[i].Length，時間複雜度為O(n * m * k)。
  • 空間複雜度：要建立DP結果的空間，因此空間複雜度為O(n)。

學習重點

  • Dynamic Programming
Last Updated:
Contributors: eisen