139. Word Break

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.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

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

Solution

(1) Java

(2) Python

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        if not s:
            return False
        length = len(s)
        dp = [False]*(length)
        for i in range(0,length):
            if s[:i+1] in wordDict:
                dp[i] = True
            else:
                for j in range(i):
                    if dp[j] and s[j+1:i+1] in wordDict:
                        dp[i] = True
                        break
        return dp[length-1]

(3) Scala