1 題目描述

這題簡單來說就是給定一個字串s和一個字典wordDict，判斷s是否可以被空格分割成一個或多個在字典中出現的單詞。

2 解法

2.1 我的作法

但是這個為什麼說他是一個dp問題，是因為他就像背包問題一樣，s是背包，wordDict是物品，我們要看看s能不能裝下wordDict裡面的物品。如果裝錯物品可能導致裝不下。
我的想法一開始是一個用切割的方式切成兩塊，然後把所有可能的組合都存到字典裡面，最後找到可以把目前切割結果組合成s的組合。

切割成兩塊

  • 例如：applepenapple
  1. a + pplepenapple
  2. ap + plepenapple
  3. app + lepenapple
  4. …
1
2
3
for i in range(1, n):
    check_w = word[0:i]
    rest_w = word[i:n]

如果找到一組，切成兩塊的結果都是True就找到了

  • 假設helper是一個可以判斷是否可以切割成wordDict的函數
  • 關係式：helper(word[0:i]) and helper(word[i:n])
1
2
3
4
5
for i in range(1, n):
    check_w = helper(word[0:i])
    rest_w = helper(word[i:n])
    if check_w and rest_w:
        return True

終止條件

  • 我們需要一個字典來存放已經切割過的結果，避免重複計算
  • 如果是空字串，就是True
1
2
3
4
5
6
7
8
9
10
11
12
# 如果是空字串或是在wordDict裡面，就是True
if "" or s in wordDict:
    return True

# 如果已經計算過，就直接返回
if s in dp:
    return dp[s]
for i in range(1, n):
    check_w = helper(word[0:i])
    rest_w = helper(word[i:n])
    if check_w and rest_w:
        return True

最後

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    """
    time: O(n^2)
    - T(n)=T(n-1)+T(n-2)+...+T(1)，這是一個等比數列，總和為 O(n^2)。
    space: O(n)
    - 使用了一個長度為 n 的字典來存儲已經計算過的結果。
    """
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        def helper(word: str) -> bool:
            if word == "" or word in wordDict:
                return True
           if word in dp:
                return dp[word]

            n = len(word)
            for i in range(1, n):
                check_w = word[0:i]
                rest_w = word[i:n]

                dp[check_w] = helper(check_w)
                dp[rest_w] = helper(rest_w)

                if dp[check_w] and dp[rest_w]:
                    return True
            return False

        dp = dict()
        return helper(s)

可見這個solution的時間複雜度是O(n^2)，空間複雜度是O(n)。不太好．．．

2.2 優化

我們想一下，如果今天有個共同重要的是，我們需要從index=0開始找s的每一種長度的字串，是否滿足在wordDict裡面，舉例來說，我們希望dp紀錄的是，不同狀態的s是否可以被wordDict裡面的字串組合而成。

  • dp[apple] = True 我們可以用長度來代表不同的狀態，例如可以寫成這樣dp[5] = True，這樣就可以s的前面5個字元是否可以被wordDict裡面的字串組合而成。
  • dp[applepen] = True = dp[9] = True
  • 其他狀態就是False，除了dp[0] = True，因為空字串是True

初始化 + 終止條件

1
2
3
4
5
6
7
dp = [True] + [False] * (len(s) + 1)

for i in range(len(s)):
    check_w = s[i]
    for w in wordDict:
        if check_w == w:
            dp[i] = True

但是我們會發現一個問題，就是當找到apple的時候，我們要繼續往後比較penapple該怎麼做？如果我們知道i的位置是True，我們繼續往後比較時，我們可以直接從i的位置開始比較，這樣就可以省下很多時間。

然後我們的dictWord=['apple', 'pena','pen']這三組好了，我很喜歡用這個例子，因為如果你先選了pena，那麼可能會因為邏輯錯誤無法回傳True(apple, pen)的組。

  1. 我們目前已經確定apple前五個字dp[5]=True
  2. 然後我們會需要走到s[i:len(w)]開始看從apple之後的文字數加上len(w)是否等於w
    1. 就像是目前w是pena
    2. i 是 5
    3. s[i:i+len(w)] 是 pena
  3. 然後我們檢查s[i:i+len(w)]是否等於w，如果是的話，我們就可以把dp[i+len(w)]設為True，也就是目前的長度applepena 是滿足的，寫成 dp[9] = True
  4. 但是在i+len(w)的時候要注意不要超過len(s)的長度喔，否則會發生index out of range的問題。
  5. 最後回傳dp[-1]就是我們的答案，也就是長度最長的那個字串是否滿足。
1
2
3
4
5
6
7
8
9
10
11
12
13

dp = [True] + [False] * (len(s) + 1)

for i in range(len(s)):
    for w in wordDict:
        # note1: 只有當dp[i]是True的時候，我們才需要繼續比較，也就是說`apple`（i=0:4）之前都不用比較，因為已經找到最佳解
        if dp[i]: 
            if i+len(w) <= len(s):      # note4: 注意不要超過s的長度
                check_w = s[i:i+len(w)] # note2: 從最佳解之後的字串開始比較，只取出跟wordDict一樣長度的字串
                if check_w == w:
                    dp[i+len(w)] = True

return dp[-1]   # note5: 最後一個就是最佳解

寫乾淨一點

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
"""
time: O(n*m)
- 從 i 到 len(s) 的時間複雜度是 O(n)
- wordDict裡面有m個字串，所以時間複雜度是 O(n*m)
space: O(n)
- 使用了一個長度為 n 的字典來存儲已經計算過的結果。
"""
def wordBreak3(self, s: str, wordDict: List[str]) -> bool:
    dp = [True] + [False] * len(s)
    for i in range(len(s)):
        for w in wordDict:
            if dp[i]:
                if i + len(w) <= len(s) and s[i:i+len(w)] == w:
                    dp[i+len(w)] = True
    return dp[-1]

3 總結

這題我真的想了很久，一整天都在慢慢沈澱這個問題…dp真不簡單，真的很難想到怎麼用for loop的方式實現。這種類似背包問題，就是要想辦法找到前一步的最佳解，例如，在applepenapple中，如果比較到i=5時，我們要知道以當前的狀態最佳解是i=4時，所以應該考量的是i=4 + 當前的字串，是否可以更新目前得最佳解？舉例來說：

  • 比較apple的時候，更新最佳解dp[5]=True
  • 比較applep的時候
    • 因為最佳解是dp[5]=True
    • 所以我們可以從i=4開始往後到目前的i=5考慮是否能夠更新最佳解
    • 因為s[4:5]=p不滿足任何wordDict的字串，所以dp[6]=False
  • 比較applepe的時候
    • 因為最佳解是dp[5]=True
    • 所以我們可以從i=4開始往後到目前的i=6考慮是否能夠更新最佳解
    • 因為s[4:6]=pe不滿足任何wordDict的字串，所以dp[7]=False
  • 比較applepen的時候
    • 因為最佳解是dp[5]=True
    • 所以我們可以從i=4開始往後到目前的i=8考慮是否能夠更新最佳解
    • 因為s[4:8]=pen是滿足wordDict的字串，所以dp[8]=True
  • 比較applepena的時候
    • 因為最佳解是dp[8]=True
    • 所以我們可以從i=7開始往後到目前的i=9考慮是否能夠更新最佳解
    • 因為s[7:9]=a不滿足任何wordDict的字串，所以dp[9]=False
  • 比較applepenap的時候
    • 因為最佳解是dp[8]=True
    • 所以我們可以從i=7開始往後到目前的i=10考慮是否能夠更新最佳解
    • 因為s[7:10]=ap不滿足任何wordDict的字串，所以dp[10]=False
  • 比較applepenapp…以此類推