139. 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:

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

 def wordBreak(s: str, wordDict: List[str]):       

    word_set = set(wordDict)

    dp = [False] * (len(s) + 1)

    dp[0] = True

    for i in range(1, len(s) + 1):

        for j in range(i):

            if dp[j] and s[j:i] in word_set:

                dp[i] = True

                break

               

    return dp[len(s)]