---
# System prepended metadata

title: 139. Word Break
tags: [string, Leetcode, medium, python, Top 100 Liked Questions, dynamic programming]

---

###### 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:
``` 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)
```