LC 0139 [M] Word Break - ALawliet/algorithms GitHub Wiki

similar to LIS

• loop through each character while checking each word
• try to find a valid word at that index minus the length of the current word we're checking
• if we found a valid word, try "erasing" that word, and see if the remaining string before it can also be broken (or we're already at the head and there are no more characters left to check)

each DP cell answers the subproblem "is this string breakable to this index so far?"

"leetcode"

i = 3
is "leet" a word and is the remaining string "leet"-"leet" = "" a word or empty?
=> T[3] = True
...
i = 7
is "code" a word and is the remaining string "leetcode"-"code" = "leet" a word or empty?
=> T[7] = True

T[i] = found some word here and the string before that word was also breakable or empty

 0  1  2  3  4  5  6  7
[F, F, F, T, F, F, F, T]
 l  e  e  t  c  o  d  e

the trickiest part of this problem is just keeping the indexes straight :P

---

 0  1  2  3  4  5  6  7
[1, 0, 0, 1, 0, 0, 0, 1]
 l  e  e  t  c  o  d  e

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        
        T = [0] * (n+1)
        T[0] = 1

        for r in range(1, n+1):
            for l in range(r):
                if T[l] and s[l:r] in wordDict:
                    T[r] = 1
                    break # not needed but speeds it up
                    
        return T[-1]

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        T = [False] * len(s)

        for i in range(len(s)):
            for word in wordDict:
                i_start_word = i - len(word) + 1
                i_before_word = i_start_word - 1

                if s[:i+1].endswith(word):
                    if T[i_before_word] == True or i_before_word < 0:
                        T[i] = True
                
        return T[-1]