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. You may assume the dictionary does not contain duplicate words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
The wordDict parameter had been changed to a list of strings (instead of a set of strings).
Please reload the code definition to get the latest changes.
class Solution(object): def wordBreak(self, s, wordDict): """ :type s: str :type wordDict: List[str] :rtype: bool """ n = len(s) dp = [False] * n for word in wordDict: if s.startswith(word): dp[len(word)-1] = True for i in range(n): for j in range(i + 1): if dp[j]: if s[j+1:i+1] in wordDict: dp[i] = True if dp[n-1]: return True return False