139. Word Break

# Medium

The problem is where to cut in this string. Record from start to end, if the substring [0: i] can do word break. The result is [0: len(s)-1].

Solution:

1. Define a list canSegement[False]*(len(s)+1) to do DP, set canSegement[0]=True.

2. Two-layer for loop to fill in all elements of canSegment. Cut from [0:i], if substring before cut can segement and substring after cut is contained in wordDic, then canSegment[i]=True.

3. canSegment[len(s)] is the result.

Because canSegment[j] = True and {pe} is not in wordDic, canSegment[i] = False

Python

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        canSegment = [False]*(len(s)+1)
        canSegment[0] = True
        
        for i in range(1, len(s)+1):
            for j in range(0, i):
                if canSegment[j] == True and s[j:i] in wordDict:
                    canSegment[i] = True
                    break
                canSegment[i] = False
            
        return canSegment[len(s)]

Java(O(n^3)

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] canSegment = new boolean[s.length() + 1];
        Arrays.fill(canSegment, false);
        canSegment[0] = true;
        
        for(int end = 1; end <= s.length(); end ++)
            for(int start = 0; start < end; start ++) {
                if(canSegment[start] && wordDict.contains(s.substring(start, end))) {
                    canSegment[end] = true;
                    break;
                }
            }
        return canSegment[s.length()];
    }
}