Word Break Problem Dynamic Programming

And where is the dictionary.

String="iamace" Words=[i, am, ace]
1) take array of length of the string+1.and first cell is empty string.
2) take first character check in Words it's there or not.
If yes empty string in the cell.
If no that character plus previous cell string and keep in the cell.
3) if not empty string in cell check any word in Words is matching with it or not if match empty string in cell or keep as it is.
4) continue for rest character.
5) in the last cell if it's empty then successful else not.

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

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

bit confusing

So you are the Fire Fist Ace

Worst explaination.

what is the time complexity?
O(n^4) cause string matching will take O(n) and O(n^3) for filling the matrix

Yeah as people pointed out, you seem to be operating with a reduced/arbitrary dictionary. For example, I would identify {I, a, am, ma, mac, ace, mace} as the dictionary ("ma" as in mother). The real value of the word break problem, I think, is to show that you can arrive at multiple valid solutions ("I a mace"/"I am ace"). In this case it's not the job of DP to actually choose which solution is better, so by reducing your dictionary I think you missed out on that teaching opportunity. Just saying.

How many of u r watching in this Lockdown

awesome brother ...

Not one of your best videos Tushar

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.

This can be done in a 1D array of DP instead of 2D DP array.

I,am,a,ace are words in the dictionary

Is nobody going to talk about how he just disregarded "mac" and said it doesn't exist. Lol he works in apple too.










It's a joke ppl get yo burnt ass outta here

What is the time complexity????

thanks a lot sir you really helped me in this question, once again thanks

Here's my C++ O(n) space solution:
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n=s.size();

bool dp[n+1];
memset(dp,0,n+1);

dp[0]=1; int end;

for(int start=0;start<n;start++)
{
if(!dp[start])
continue;

for(string word:wordDict)
{
end=start+word.length();
if(s.substr(start,word.length())==word)
dp[end]=1;
}
}

return dp[n];
}
}

Nice. It can also be done with 1-D array. If anyone is looking for that, here it is. Took me a while to figure out.
s-input string, dict- dictionary converted to hashset.

boolean[] f = new boolean[s.length() + 1];

f[0] = true;
for(int i=1; i <= s.length(); i++){
for(int j=0; j < i; j++){
if(f[j] && dict.contains(s.substring(j, i))){
f[i] = true;
break;
}
}
}
return f[s.length()];

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

Dictionary is - {I,A,am,ace}

Yes we use dynamic programming to solve this !

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 WordBreakProblemTabulation(string 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 (dictionary.Contains(substring)) // 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
}
}

What would be the time complexity of this solution?

slower soln

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

This can be solved using 1-D dp.

perfect explaination . Dictionary is "i, am, a, ace" (mentioning this for the ones who understood the approach but did not got whats the dictionary) lol

Please my friends Dislike the video

Below code might be helpful for the viewers.

class Sol
{
public static int wordBreak(String A, ArrayList<String> B )
{
int n = A.length();
int dp[][] = new int[n][n];

HashSet<String> Dic = new HashSet<>(B);

int k=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n && k<n && j+k<n;j++)
{
String w = A.substring(j,j+k+1);
if(Dic.contains(w))
{
dp[j][j+k] = 1;
continue;
}


for(int x =j; x<j+k ; x++)
{

if( dp[j][x]==1 && dp[x+1][j+k]==1)
dp[j][j+k]=1;

}

}
k++;

}
return dp[0][n-1];
}
}

please add recursion tree in your video too...

it's 6x6 matrix not 5x5

Bhai dictionary kaha hai tumhara ?

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

DP will be the death of me!!

Thanks a lot!!! Very well explained.

This has to be one of the worst Work Break explanations. first of all the DP matrix you are Say A is a word in the dictionary... What Dictionary? then you say C isn't?

where is dictionary ???

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

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

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

I just love you man. Brilliant

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.

where is the dictionary😒😒

Don't learn DP from this guy, you won't be able to develop the intuition.

what is the string and what is the dictionary ?

There is a bug on solution for this video on github on method at line #60 - one line 73 you are subscring too much

where is the fucking dictionary