139. Word Break.md

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

自己写的方法code1超时了QuQ

code2来自discussion，动态规划十行不到啊好好想一下啊！！

3/11 code2的java版本

Code1

def wordsplit(s, wordDict, flag, min_len, max_len):
    if len(s) == 0 or s in wordDict:
        # print("Yes!")
        flag = True
    elif len(s) < min_len:

    else:
        for l in range(min(len(s)-1,max_len),min_len-1,-1):
            if s[:l] in wordDict:
                flag = wordsplit(s[l:],wordDict, flag, min_len, max_len)
                if flag:
                    return flag
    return flag
    
    
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        min_len = 1e5
        max_len = 0
        flag = False
        for word in wordDict:
            min_len = min(min_len,len(word))
            max_len = max(max_len,len(word))
        # print(min_len)
        
        flag = wordsplit(s,wordDict, flag, min_len, max_len)
        return flag

Code2

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        f = [False for i in range(len(s))]
        f.insert(0,True)
        # print(f)
        for i in range(len(s)+1):
            for j in range(i):
                if f[j] and s[j:i] in wordDict:
                    f[i] = True
        return f[i]

Code2 - Java

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet(wordDict);
        boolean[] table = new boolean[s.length()+1];
        table[0] = true;
        
        for(int i=0;i<=s.length();i++)
            for(int j=i;j<=s.length();j++)
            {
                // System.out.println(s.substring(i,j));
                if(set.contains(s.substring(i,j)) && table[i] == true)
                    table[j] = true;
            }
        return table[table.length-1];
    }
}