Word Break Problem

In this video, the speaker discusses the "Word Break" problem. The problem involves breaking an input string into separate strings such that every separate string in s is also found inside of a given word dictionary.

Brute Force Approach

• One approach to solving the problem is to try every possible prefix of the input string and check if it exists in the word dictionary.

• Once a matching prefix is found, we can recursively solve for the remaining portion of the input string.

• This approach has a time complexity of O(n^2 * m), where n is the size of the input string and m is the size of the word dictionary.

More Efficient Approach

• Another approach involves checking every word in the word dictionary as a potential prefix for the input string.

• If a matching prefix is found, we can recursively solve for the remaining portion of the input string starting from that position.

• This approach has a time complexity of O(n * m * n), which is more efficient than brute force when m < n.

Conclusion

The "Word Break" problem involves breaking an input string into separate strings that are also found in a given word dictionary. Two approaches were discussed: brute force and more efficient. The more efficient approach involves checking every word in the dictionary as a potential prefix for the input string.

Decision Tree Approach

In this section, the speaker explains how to use a decision tree approach to solve the word break problem.

Backtracking Solution

• The subproblem is finding words that can match the remainder of the string.

• We will have decisions in our decision tree based on the number of words in the word dictionary.

• When we try a word and it doesn't match, we won't continue down that path.

Caching

• If we ever return false from a function call, we want to cache that result so we don't need to redo all of that work if we try the same exact thing again.

• Our base case is going to be dp of 8 because it's the length of the string.

Bottom-Up Approach

• We're going to do a bottom-up approach where we go through every single index in reverse order.

• We would start at the last character and see if we can word break the remainder of this string by trying every single word in our dictionary.

Dynamic Programming Solution

In this section, the speaker explains how to use dynamic programming to solve the word break problem.

DP Solution vs. Caching

• The DP solution is usually less code than caching.

• We're going to be looking at our input string neat code.

DP Algorithm

1. Create an array dp with size n+1 where n is length of input string

2. Set dp= true

3. Iterate over each index i from 1 up until n:

• For each index j from 0 up until i:

• Check if dp[j] is true AND substring from j up until i exists in dictionary

• If both conditions are met, set dp[i] = true and break out of inner loop

4. Return dp[n]

Time Complexity

• The time complexity of the DP solution is O(n^2) because we have two nested loops.

• However, since we're only checking substrings that exist in our dictionary, it's actually closer to O(n*m) where m is the size of our dictionary.

Conclusion

In this section, the speaker concludes the video by summarizing what was covered and providing some final thoughts.

• We learned how to solve the word break problem using both a decision tree approach and dynamic programming.

• The DP solution is more efficient than caching because it requires less code.

• The time complexity of the DP solution is O(n^2), but it's closer to O(n*m) in practice.

• It's important to understand both approaches because sometimes one may be more appropriate than the other depending on the problem.

Dynamic Programming Solution

In this section, the speaker explains how to use dynamic programming to solve the word break problem.

DP of 3, 2 and 1 are False

• The speaker explains that if we start at certain positions in the string, we won't be able to match any words in our dictionary.

• DP of 3 is false because we can't match any words starting at that position.

• DP of 2 is also false for the same reason.

• DP of 1 is also false because there are no matching words starting from that position.

DP of Zero is True

• The speaker explains that if we start at index zero, we can match a portion of the string with a word in our dictionary.

• We want to know if we can break the entire string starting at index zero.

• Using dynamic programming, we compute dp of four and find it to be true.

• We set dp of zero equal to true as well.

Code Implementation

• The cache used for this implementation will be a one-dimensional array initialized to false with length s + 1 where s is the length of the input string.

• We initialize our base case by setting dp[s] = true since it's out-of-bounds and doesn't need computation.

• We iterate through every position i in s from end-to-start using a decrementer (-1).

• For each i, we try every single word in our dictionary and check if it matches with s[i:i+len(w)] (w being the current word).

• If it does match, then dp[i] = dp[i + len(w)] (relationship derived earlier).

• If dp[i] becomes true after trying all words in dictionary, then stop iterating over i.

• Return dp.