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)