How to solve the word break problem using dynamic programming : step by step explanation

Another addition to our dynamic programming tutorial series, the classic word break problem. You'll learn to make a dynamic programming algorithm to solve this word break problem
step by step.

But before you proceed, I just want you go through the following videos in order
1. Intuition to longest palindromic subsequence

2. Longest palindromic subsequence

3. Longest palindromic substring

4. Palindrome partitioning problem

After you have gone through these videos then I guarantee that the solving the word break problem will become a piece of cake for you.

With this let's look at the problem statement of the word break problem which can also be called a cousin of palindrome partitioning problem.

So, you're given a string 'i l i k e i c e' as well as a dictionary which has certain words [i, am, like, boy, ice]

If you put some splits at the right places then you're going to get substrings or segmented strings; all you need to find out if those substrings are present in the dictionary given to you.
and if they are, then you can say that the string given to you once segmented contains all substrings which are present in the dictionary.

i | l i k e | i c e

If you observe the line above then there is one split which I have put after 'i' and another one after 'e' which have segmented the string into i, like, and ice all of which are
present in the dictionary.

And yes since this is a part of our dynamic programming tutorial hence we will consider it as our good old DP problems and will solve it using the bottom-up approach.

So tune in to this video in order to add one more fantastic computing problem to your bucket list.