###### tags: `Leetcode` `medium` `dynamic programming` `string` `python` `Top 100 Liked Questions`

# 139. Word Break

## [題目連結:] https://leetcode.com/problems/word-break/

## 題目:
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.

* ```s``` and ```wordDict[i]``` consist of only lowercase English letters.
* All the strings of ```wordDict``` are **unique**.

**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能否拆分成wordDict內的字串:
* 即為能否利用wordDict內的字串組合出s
* 使用Dp:
* dp[i]表示字符串s[:i] (前i個字符)是否可拆分
* dp[len(s)]即為res
* 對於dp[i]:
* 遍歷所有word:
* for word in wordDict:
* 判斷條件:
* 1.)dp[i-len(word)]== True
* 2.)s[0:i]中 最後len(word)個字==word
* 兩者皆成立，dp[i]=True, then break
* 因為有任一個word符合即可

## Python:

class Solution(object):
    def wordBreak(self, s, wordDict):
        #dp[i]表示s[:i]是否可分
        dp = [ False for _ in range(len(s)+1)]
        dp[0]=True
        for i in range(1,len(s)+1):
            for word in wordDict:
                """
                判斷條件:
                1.)dp[i-len(word)]==True
                2.)s[0:i]中 最後len(word)個字==word
                """
                n = len(word)
                if dp[i-n]==True and s[i-n:i]==word:
                    #有word符合就好 
                    dp[i]=True
                    break
        return dp[-1]
result = Solution()
s = "leetcode"
wordDict = ["leet","code"]
ans = result.wordBreak(s,wordDict)
print(ans)