Word Break Problem Dynamic Programming

Given a string and a dictionary, return true if string can be split into multiple words such that each word is in dictionary. If not return false

[alishoman]

I think dictionary is {"I", "am ", "ace", "a" }

[yushdecides]

Lol I can't believe he explained the whole question without telling the exact dictioniory

[muskanroxx]

Tushar: "yes we will use dynamic programming to solve this"
me: but why?
Tushar: "keh diya na, bas, keh diya"

You should have also mentioned your dictionary.

[mickychan]

This is what real content on education looks like on the internet. No funky thumbnails with faang logos, nor any kind of fake publicity. Just professional teaching. Hats off Sir and Thank you

[amarnathprasad]

Wife: Honey, I've got myself into a prob...
Tushar: Yes, we will use dynamic programming to solve this problem.

[bhavukmathur]

I've never left your video unsatisfied. Great work, thanks :)

[niyatitiwari]

Thank you so much for the lectures. I have been trying to understand DP for ages now, never found better explanations. Finally got a grasp on how to approach the problems.

[shivankchaturvedi]

the best explanation except it took me time to understand what is in the dictionary

[starc]

bro please read is saying same thing, just put it (your holy dictionary )in the discription atleast

[alanliang]

tushar litterally can solve any problem in the world with his table

[jaatharsh]

thanks again for superb video but found a couple of issues with ur code for Tabulation method & especially Printing but thanks for explaining the solution enough so i was able to figure out the required change.
Solution in C#
// Bottom-Up Tabulation based solution // Time O(n^3) || Space O(n^2)
// Function which returns true if for given input there exists such a set where each substring is present in the dictionary & also prints selected Words
// Ex: for string "code" returns true if dictionary contains 'c', 'od', 'e' or excat word "code"
public static bool input, HashSet<string> dictionary)
{
var len = input.Length;
if (input == null || len < 1) return false;

int[, ] tab = new int[len, len];

for (int i = 0; i < len; i++)
for (int j = 0; j < len; j++)
tab[i, j] = -1; // set default -1 to indicate word/substring of words not found in Dictionary

for (int size = 1; size <= len; size++) // size of current substring start from 1 to entire length of input
for (int i = 0; i <= len - size; i++) // start index in input from where we consider substring
{
int j = i + size - 1; // last index in input till where we consider substring
var substring = input.Substring(i, size); // extract string for ease of use

if // if given substring exists in dictionary mark this True and continue onto next string
{ tab[i, j] = j; continue; }

// looking for an index i.e. 'splitAT' so that both left & right substring return true
for (int splitAt = i; splitAt <= j; splitAt++)
if (tab[i, splitAt] != -1 && tab[splitAt + 1, j] != -1)
{ tab[i, j] = splitAt; break; }
}

// if subsets of words for input which exists in Dictionary found print them & return True
var found = tab[0, len - 1] != -1;
if (found) PrintWordsInWordBreakProblem(tab, input, len);
return found;
}

// Time O(n)
public static void PrintWordsInWordBreakProblem(int[, ] arr, string input, int len)
{
Console.Write($"\n Words which were found in dictionary are: \t");
int i = 0, j = len - 1, k;
while(i<=j)
{
k = arr[i, j];
if (j == k) // entire word found, print word & exit
{
Console.Write($" \t{input.Substring(i, j - i + 1)}");
break;
}
else // else print left half n to continue to search for remaining words in the right half
{
var p = Math.Max(k, 1); // needed hence we are printing character on 0th index hence add 1 to length
Console.Write($" \t{input.Substring(i, p)}");
}
i = k + 1; // keeping interating on right half
}
}

[pittala]

The intuition for splitting a[i][j] at k, can be better explained like this:

In a[i][j], start looking from indexes m, n, ... for words of different lengths: a[i][i], a[i+1][j], then a[i][i+1], a[i+2][j] ... until a[i+j-1][aj][j], like how we would search in a given long word. Lets say there are two splits with valid first word. Lets call them splits at m & n. We would then check whether a[m+1][j] or a[n+1][j] is valid by checking into the previously computed matrix (bottom up order)

[princeakhil]

Yes we use dynamic programming to solve this !

[prekshakoirala]

Can we also use recursion with memoization for this problem?

[kkaabbccdd]

I would expect you to explain why you choose DP. Second explain what does the 2-D matrix is built on and why storing Bool values in it.

[kaustubh]

What is the worst case complexity for this solution? Is it O(n^3), since there are 3 loops?

[Derpocracy]

"does MACE belong to the dictionary? no, let's say no"

[infinitequest]

Hi Tushar,
Nice vid! But it would be more helpful to understand if you could walk through the code posted on your github account. Thanks

[JoffreyB]

It would've been nice if you actually wrote what IS the dictionary you're talking about. I mean explicitly specify the words in a dictionary and a dictionary itself. Otherwise you're just giving the input word and I personally have no idea with what dictionary words you're doing your matching, because I see only 1 input word.