Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = “leetcode”, wordDict = [“leet”,“code”] Output: true Explanation: Return true because “leetcode” can be segmented as “leet code”. 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. Example 3:

Input: s = “catsandog”, wordDict = [“cats”,“dog”,“sand”,“and”,“cat”] Output: false

解題思路:

不在多贅述暴力破解法，可以使用動態規劃來解題，我們定義一個陣列為 s 的長度，這陣列的每個元素代表 s 的前 i 個字元是否可以被拆解成 wordDict 的字元。

題目範例: s = andrew, wordDict = [and, dre]

[1,0,0,0,0]

最後我們會得出:

[1,0,0,1,0,0,0]

arr[3] 為 True 代表著 andrew 的前 3 個字元 and 可以被拆解成 wordDict 的字元。

問題

那 … dre 為什麼不能是 True ? 確實 dre 也在 andrew 之中，但 arr[2] 也就是 an 並不能被拆解，所以就算 dre 在 andrew 之中，但 andrew 並不能被拆解成 an 與 dre。

這時我才看懂解法是 每個陣列元素中 都代表著 s 的前 i 個字元是否可以被拆解成 wordDict 的字元，再判斷 從 i+1 (也就是可被拆解的字元) 到目前位置是否可被拆解，再由 arr[-1] 最後一直判斷所有解是否成立。

Code Example

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        for i in range(1, n + 1): # 掃秒所有字元
            for j in range(i):    # 前面的字串是否被拆解
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break
        return dp[-1]