https://leetcode.com/problems/word-break/
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
- DP, dp[i] means s[:i+1] can be segmented into words in the wordDicts
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False for _ in range(len(s) + 1)]
# dp[i] means s[:i+1] can be segmented into words in the wordDicts
dp[0] = True
for i in range(len(s)):
for j in range(i, len(s)):
if dp[i] and s[i:j+1] in wordDict:
dp[j+1] = True
return dp[-1]