# 0139. 單詞拆分 ## 題目地址(139. 單詞拆分) <https://leetcode-cn.com/problems/word-break/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個非空字符串 s 和一個包含非空單詞的列表 wordDict，判定 s 是否可以被空格拆分為一個或多個在字典中出現的單詞。 說明： 拆分時可以重復使用字典中的單詞。 你可以假設字典中沒有重復的單詞。 示例 1： 輸入: s = "leetcode", wordDict = ["leet", "code"] 輸出: true 解釋: 返回 true 因為 "leetcode" 可以被拆分成 "leet code"。 示例 2： 輸入: s = "applepenapple", wordDict = ["apple", "pen"] 輸出: true 解釋: 返回 true 因為 "applepenapple" 可以被拆分成 "apple pen apple"。 注意你可以重復使用字典中的單詞。 示例 3： 輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 輸出: false ``` ``` ## 前置知識 - [動態規劃](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這道題是給定一個字典和一個句子，判斷該句子是否可以由字典里面的單詞組出來，一個單詞可以用多次。 暴力的方法是無解的，復雜度極其高。 我們考慮其是否可以拆分為小問題來解決。 對于問題`(s, wordDict)` 我們是否可以用(s', wordDict) 來解決。 其中 s' 是 s 的子序列， 當 s'變成尋常(長度為 0)的時候問題就解決了。 我們狀態轉移方程變成了這道題的難點。 我們可以建立一個數組 dp, dp\[i\]代表 字符串 s.substring(0, i) 能否由字典里面的單詞組成， 值得注意的是，這里我們無法建立 dp\[i\] 和 dp\[i - 1\] 的關系， 我們可以建立的是 dp\[i - word.length\] 和 dp\[i\] 的關系。 我們用圖來感受一下：  沒有明白也沒有關系，我們分步驟解讀一下： （以下的圖左邊都代表 s，右邊都是 dict，灰色代表沒有處理的字符，綠色代表匹配成功，紅色代表匹配失敗）     上面分步解釋了算法的基本過程，下面我們感性認識下這道題，我把它比喻為 你正在`往一個老式手電筒??中裝電池`  ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {string} s * @param {string[]} wordDict * @return {boolean} */</span> <span class="hljs-keyword">var</span> wordBreak = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">s, wordDict</span>) </span>{ <span class="hljs-keyword">const</span> dp = <span class="hljs-params">Array</span>(s.length + <span class="hljs-params">1</span>); dp[<span class="hljs-params">0</span>] = <span class="hljs-params">true</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < s.length + <span class="hljs-params">1</span>; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> word <span class="hljs-keyword">of</span> wordDict) { <span class="hljs-keyword">if</span> (word.length <= i && dp[i - word.length]) { <span class="hljs-keyword">if</span> (s.substring(i - word.length, i) === word) { dp[i] = <span class="hljs-params">true</span>; } } } } <span class="hljs-keyword">return</span> dp[s.length] || <span class="hljs-params">false</span>; }; ``` ``` **復雜度分析** - 時間復雜度：O(N2)O(N ^ 2)O(N2) - 空間復雜度：O(N)O(N)O(N) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。