Leetcode - Word Break

Question

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.

Idea

• Same idea as Leetcode - Coin Change where we have a dp array, where we want to know if our entire string can be broken by asking can its substrings be broken down?
• Our base case here is that dp[len(s)+1] = True meaning if we go out of index we can break the word
• Iterating backwards, for each position in the string we check each word in wordict for a match of s[i:i+len(w)] and if True, we set our current index’s cache to the result of dp[i+len(w)], which will resolve to true if we can match a word (since our index will be right before the start of the matched word, + its length will take us to our base case of True)
• If at any time we get to a True result, we break out of the loop
• dp[0] will hold the solution since we go backwards

Solution