Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

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

Intuition

To compare to see if a word contains the word inside wordDict, we might think of Trie. However using Trie might increase the complexity because if a search fail, we need to reset from the beginning of the Trie node.

Maybe the idea of using Trie could be for optimisation if we have time.

For this question, we need to see weather we should start comparing from the string s or from the wordDict

So one example might be whenever we see a word we can mark the appearance

s = catsandog, wordDict = [cats, dog, sand]
    1111
       1111
          111

However doing this make it hard to merge to get the result.

It would be better if we start from string s itself and see which word we can form at each index

Word dict = ['cats', 'seat', 'cat', 'dogs', 'ogs', 'eats']

catseatsdogs
FFFFFFFFFFFF # This array represents if we can form a word at a index
               By default we should have everything False

v
catseatsdogs
FFFFFFFFFFFF

At position `c`, we can have either `cats` or `cat`, therefore
we mark these position as `T`

v
catseatsdogs
FFTTFFFFFFFF  # So we mark index 2 and 3 represents for `cat`
                and `cats` true
                

 v
catseatsdogs
FFTTFFFFFFFF   # At `a` there is no word we can form starting from `a`

  v
catseatsdogs
FFTTFFFFFFFF  # No word can form here either
   v
catseatsdogs
FFTTFFFFFFFF  # at `s` we can form `seat`, but we have to check 
                if the index before we can form a word (cat)
                
                since we can form cat, we mark `seat` as true

                The reason why we need to check this is the 
                dp array should have the final result therefore
                we need to check all the previous combination if it's [[Validate Binary Search tree]]


    v
catseatsdogs
FFTTFFFTFFFF   # at e we can form `eats`, we check if `cats`
                is a valid word, we then mark as True for `eats`


     v
catseatsdogs   # at a there is no word we can form
FFTTFFTTFFFF


      v
catseatsdogs   # at t there is no word we can form
FFTTFFTTFFFF

       v
catseatsdogs   # at s there is no word we can form
FFTTFFTTFFFF


        v
catseatsdogs   # at d we can form dogs, we check if before `d`
FFTTFFTTFFFF     we can form any words, which is True so we mark
                `dogs` as true 


         v
catseatsdogs   
FFTTFFTTFFFT  # At o we can form `ogs`, we check if there is 
                a word can form before `ogs` which is False,
                so we do nothing for `ogs`

          v
catseatsdogs   
FFTTFFTTFFFT   # at g there is no word we can form


           v
catseatsdogs   
FFTTFFTTFFFT   # at s there is no word we can form


We return dp[-1] which is the last result of `True`

Implementation

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False for i in range(len(s))]

        for i in range(0, len(dp)):
            for word in wordDict:
                if s[i: i + len(word)] == word and (dp[i - 1] or i - 1 < 0):
                    dp[i + len(word) - 1] = True

        return dp[-1]

Time complexity: $O(n * w)$

• $n$ to loop through all the word list
• $w$ to compare a word with s

Space complexity: $O(n)$