# [Word Break](https://leetcode.com/problems/word-break/solution/)
###### tags: `Leetcode`, `Medium`, `Dynamic Programming`

## Approach

* Initialize `dp` array to one more than the length of the string, set all the values to `False` and set the last value to `True`.
* Iterate backwards in the string
* For every word in the dictionary, check the same length of substring from the current index position and check if it matches the word.
* If it matches then set the value of `dp[index] = dp[index + len(word)]`
* If it does not match with any of the words in the dict, then continue with the for loop and shift index one place to the left
* Return `dp[0]`

## Asymptotic Analysis
### Time Complexity: **O(M.N²)**
### Space Complexity: **O(M)**
M=Length of the string
N=Length of the dictionary
## Code

from typing import List


class WordBreak:
    def word_break(self, s: str, word_dict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[len(s)] = True
        for index in range(len(s) - 1, -1, -1):
            for word in word_dict:
                if (index + len(word) <= len(s) and 
                        s[index : index + len(word)] == word):
                    dp[index] = dp[index + len(word)]
                    if dp[index]:
                        break
        return dp[0]


input_string1, input_string2 = 'applepenapple', 'catsandog'
word_dict1, word_dict2 = ['apple', 'pen'], ['cats', 'dog', 'sand', 'and', 'cat']
wb = WordBreak()
print(f"Can '{input_string1}' be segmented? -> {wb.word_break(input_string1, word_dict1)}")
print(f"Can '{input_string2}' be segmented? -> {wb.word_break(input_string2, word_dict2)}")