0%

### 题目描述

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

### 例子

#### 例子 1

Input: `s = "leetcode", wordDict = ["leet", "code"]`
Output: `true`
Explanation: `Return true because "leetcode" can be segmented as "leet code".`

#### 例子 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.`

#### 例子 3

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

### Note

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

### 解题思路

• 对于题目中给出的 `"leetcode"``["leet", "code"]`，对于一整个单词，我们可以将它分解成不同的子问题来分别求解:
• `"leetcode" --> "l" && "eetcode"` 对于这两部分，我们只需要判断 `wordbreak("l") && dict.count("eetcode")` 是否为真即可，假如为真那么对于整个 `"leetcode"` 也可以判断为真，否则
• `"leetcode" --> "le" && "etcode"` 进行同样操作，注意由于 `wordbreak("l")` 我们已经进行过一次计算，因此在计算 `wordbreak("le")` 中时可以利用该结果节省计算时间

• 时间复杂度: O(n^2)
• 空间复杂度: O(n^2)

GitHub 代码同步地址： 139.WordBreak.cpp

GitHub: Leetcode-C++-Solution