> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/139.-word-break.md).

# 139. Word Break

## 1.問題

* 判斷用list的字串是否可以組成s

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
* function header, parameter
* test input
* 觀察
* 說明想法
  * 這個問題最直覺的做法是用DFS來列舉所有的可能性, 但會超出時間
  * 其實可以用DP的做法, 設定end, start兩指標, 等於是雙重迴圈, 搜尋start與end所截取的片段是否有在list中, 如果有且dp\[start]為真, 則讓dp\[end + 1] = true, 最後判斷dp\[size]
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if (wordDict.empty()) {
            return false;
        }
        
        unordered_set<string> mset(wordDict.begin(), wordDict.end()); 
        int size = s.size();
        vector<bool> dp(size + 1, false);
        dp[0] = true;
        for (int end = 0; end < size; end++) {
            for (int start = end; start >=0; start--) {
                if (dp[start] && mset.count(s.substr(start, end - start + 1))) {
                    dp[end + 1] = true;
                    break;
                }
            }
        }
        
        return dp[size];
        
    }
};
```

&#x20;