139.Word Break === ###### tags: `Medium` `Array` `Hash Table` `String` `DP` [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. ### 範例 **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 ``` **Constraints**: * 1 <= `s.length` <= 300 * 1 <= `wordDict.length` <= 1000 * 1 <= `wordDict[i].length` <= 20 * `s` and `wordDict[i]` consist of only lowercase English letters. * All the strings of `wordDict` are **unique**. ### 解答 #### C++ ``` cpp= class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { int n = s.size(); vector<bool> segmentable(n + 1, 0); // s[0:ed] can be segmented into wordDict segmentable[0] = true; for (int ed = 1; ed <= n; ed ++) { for (int st = 0; st < ed; st ++) { string testStr = s.substr(st, ed - st); bool found = find(wordDict.begin(), wordDict.end(), testStr) != wordDict.end(); if (segmentable[st] and found) { segmentable[ed] = true; break; } } } return segmentable[n]; } }; ``` > [name=Jerry Wu][time=4 August, 2023] #### Python ```python= class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: n = len(s) @cache def bt(i): if i == n: return True return any(bt(j+1) for j in range(i, n) if s[i: j+1] in wordDict) return bt(0) ``` > [name=Yen-Chi Chen][time=Sat, Aug 5, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)