@@LightningXThunderVlogs You have to check whether words are in dictionary or not. For that you need to have a map and store those words in that map. You can't store all the words in the English dictionary in the map manually and that's why you need to have a dictionary given in the question which this guy hasn't given.
@@LightningXThunderVlogs Bro but you can't use that in code. +, in general, when these types of questions are framed, it is assumed, a particular dictionary(given) is being followed
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
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.
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 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
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)
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.
What to do If I want to list all combinations? Like, the input string is = "Thisishugebreakthrough". The dictionary is ["This", "is", "huge", "break", "through", "breakthrough"]. Here 2 combinations are possible.
There is a problem. What if you get a dictionary of {'aa', 'aaaa'} and your word is aaaaaaa. (7 a's). The logic he described does not satisfy this case. He missed the logic condition when you check if the substring exists in the dictionary AND also check if the substring before it is also true before setting true.
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.
More than complexity. the solution with Trie is easier to understand. The problem with DP is that tomorrow if someone is reading the code its impossible to understand what the matrix update at every step is doing.
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];
Thanks Tushar. Very interesting question, nicely explained. An extension to the question could be: how do we process the input if it is really large and cannot be fetched at a time? Ex: "thisisareallylargestring" If we partition at the right place ("thisisareally" and "largestring") than it works well, but if we partition half word ("thisisareall" and "ylargestring") than its a problem. ...any thoughts?
Interesting. I have been dealing with DP matrix where you need to fill up in a strictly bottom-up manner (vertically). This is the first problem I've seen that you need to fill it up diagonal by diagonally. Great explanation though!
@@ujjvalpatel5353 a little late to the convo, but its something like this dp[0] = 1 for (i = 1; i = 1; j--) if(is_word(j, i)) dp[i] = dp[j - 1]; if(dp[str_size] == 1) printf("The string can be splitted"); else printf("The string cannot be splitted"); Also keep in mind that in my case, the string is indexed from 1.
I am sorry, this is the most confusing explanation. Not to mention the fact that there is a mistake at 3:25. When you are asking "Does 'a' belong to the dictionary?" and pointing to 0-0, while you should refer to the cell 3-3 After watching this multiple times I was not able to understand the idea and referred to another video, which uses one line of dp and is much easier to understand.
thanks Tushar for another great video. Just to emphasize - The purpose of the problem is to answer if the string can be break into words. (not like other DP problems where we need to find minimum or maximum cost, etc). However, it should be mentioned that the optional break, suggested at the end is only one option out of many possible options, that can be discovered if we keep checking for ALL possible break-points in every substring we handle
Iniyan Paramasivam look at the equation at the end, there is clearly a loop over i, inside which there is a loop over j, and further, inside j, there is a loop over k. so, n^3.
public class Solution { public int wordBreak(String s, ArrayList B) { boolean[] t = new boolean[s.length()+1]; t[0] = true; Set dict = new HashSet(B); for(int i=0; i s.length()) continue; if(t[end]) continue; if(s.substring(i, end).equals(a)){ t[end] = true; } } } return t[s.length()] ; } }
you should try to print all possible word breaks not just return true and print only one result..this problem basically belongs to backtracking and recursion..though i appreciate the dp approach
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.
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
Hello Sir, Thank you so much for the videos. Your service is definitely helping thousands of us to secure our dream job. I have a question about this solution. When I was looking at different approaches for this problem, I came across the below solution, Map memoized; String SegmentString(String input, Set dict) { if (dict.contains(input)) return input; if (memoized.containsKey(input) { return memoized.get(input); } int len = input.length(); for (int i = 1; i < len; i++) { String prefix = input.substring(0, i); if (dict.contains(prefix)) { String suffix = input.substring(i, len); String segSuffix = SegmentString(suffix, dict); if (segSuffix != null) { memoized.put(input, prefix + " " + segSuffix); return prefix + " " + segSuffix; } } memoized.put(input, null); return null; } This approach seems to be simple with time complexity of O(n^2). Could you please tell us how your solution differs from this.
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
You are solving this problem at 0(n^2 ), this is not how DP is used to solve this problem take a look at this link www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/
I think dictionary is {"I" , "am " , "ace" , "a" }
exactly
The dictionary was not defined in the problem for some reason. Thanks.
Tushar: "yes we will use dynamic programming to solve this"
me: but why?
Tushar: "keh diya na, bas, keh diya"
lol, I feel the same
Lol
Lol I can't believe he explained the whole question without telling the exact dictioniory
hahahaha
typical english dict works
@@LightningXThunderVlogs
You have to check whether words are in dictionary or not. For that you need to have a map and store those words in that map.
You can't store all the words in the English dictionary in the map manually and that's why you need to have a dictionary given in the question which this guy hasn't given.
@@yushdecides it was assumed english dict is the map in video
@@LightningXThunderVlogs Bro but you can't use that in code.
+, in general, when these types of questions are framed, it is assumed, a particular dictionary(given) is being followed
You should have also mentioned your dictionary.
@A Hero Academia Then why 'm' does not belong to dictionary ?
@@maciejgirek1241 This letter doesn't constitue a word nor an idiom, hence it doesn't belong in a dictionnary.
@Chetan no, because 'mace' and 'mac' are in the English dictionary but in his example they are not in his dictionary
@@stevenjchang Consider that it is custom dictionary. you can simulate with mace true. the solution will still work. I a mace - Valid!
@@maciejgirek1241 because 'm' is a letter and not a word. You cannot compare 'm' with 'a' because a also acts as an article which has a meaning.
Wife: Honey, I've got myself into a prob...
Tushar: Yes, we will use dynamic programming to solve this problem.
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
And where is the dictionary.
bro please read comments....................everyone is saying same thing , just put it (your holy dictionary )in the discription atleast
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.
tushar litterally can solve any problem in the world with his table
litterally can solve the halting problem with his table
Exactly! He's superb
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 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
I've never left your video unsatisfied. Great work, thanks :)
+Tushar Roy
Just a suggestion, you can have more views if you also include the algorithm at the end of the video. I guess just a single page would do.
Great then :)
Thanks for this video lesson. Where can I find your latest video of the same word segmentation problem?
the best explanation except it took me time to understand what is in the dictionary
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)
Yes we use dynamic programming to solve this !
3:25 , a is 3-3 but 0-0
Can we also use recursion with memoization for this problem?
What is the worst case complexity for this solution? Is it O(n^3), since there are 3 loops?
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.
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.
I don't understand what is repeating problem here? It would make sense if you would draw a recursion tree and spot out the repeating subproblems
Actually that is , you always not need to compute all the string if u have already computed it's subproblem and stored it.(this is funda for DP)
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
What to do If I want to list all combinations?
Like, the input string is = "Thisishugebreakthrough". The dictionary is ["This", "is", "huge", "break", "through", "breakthrough"]. Here 2 combinations are possible.
Is this solution with O(m^3) the most efficient algorithm?
no there is a solution with O(n2)
Thanks a lot!!! Very well explained.
just like Matrix chain multiplication .
There is a problem. What if you get a dictionary of {'aa', 'aaaa'} and your word is aaaaaaa. (7 a's). The logic he described does not satisfy this case. He missed the logic condition when you check if the substring exists in the dictionary AND also check if the substring before it is also true before setting true.
A mace is a weapon used in medieval combat.
What is the recurence relation, Mr. Roy?
Thanks in advance for your answer.
O(n^3)
thanks a lot sir you really helped me in this question, once again thanks
Very nice explanation . Thanks Tushar
Why is this solution O(n^3)? We're only filling half of a 2D table here, shouldn't the runtime be O(n^2)?
See the code in the description
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.
3:22 why a is considered as [0,0] ??
"does MACE belong to the dictionary? no, let's say no"
I'm gonna pretend I didn't see that
hey tushar!! how about using a trie for the same problem?? trie would result a better solution.
*****
complexity of search in a trie would be o(26*length of pattern to be searched in dictionary
)
More than complexity. the solution with Trie is easier to understand. The problem with DP is that tomorrow if someone is reading the code its impossible to understand what the matrix update at every step is doing.
Dictionary is - {I,A,am,ace}
how would you find the number of ways to express a word? My strategy was:
dp[i][j]=isAWord?1:0;
for(int k=i; k
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
I just love you man. Brilliant
Your videos are super helpful. I've been wondering though, where did you get your hoodie from?
Thanks Tushar. Very interesting question, nicely explained.
An extension to the question could be: how do we process the input if it is really large and cannot be fetched at a time?
Ex:
"thisisareallylargestring"
If we partition at the right place ("thisisareally" and "largestring") than it works well, but if we partition half word ("thisisareall" and "ylargestring") than its a problem.
...any thoughts?
But this is O(n^3) time and I came up with an algorithm that I think takes O(n^2) time.
Interesting. I have been dealing with DP matrix where you need to fill up in a strictly bottom-up manner (vertically). This is the first problem I've seen that you need to fill it up diagonal by diagonally. Great explanation though!
@Shashank Kumar You might want to check your math once again. This is an O(n^3) solution.
@@VirajMavani you got better solution?
This problem is also solavable with 1 dimension array
How ?
👀
@@ujjvalpatel5353 a little late to the convo, but its something like this
dp[0] = 1
for (i = 1; i = 1; j--)
if(is_word(j, i))
dp[i] = dp[j - 1];
if(dp[str_size] == 1)
printf("The string can be splitted");
else
printf("The string cannot be splitted");
Also keep in mind that in my case, the string is indexed from 1.
I am sorry, this is the most confusing explanation. Not to mention the fact that there is a mistake at 3:25. When you are asking "Does 'a' belong to the dictionary?" and pointing to 0-0, while you should refer to the cell 3-3 After watching this multiple times I was not able to understand the idea and referred to another video, which uses one line of dp and is much easier to understand.
What would be the time complexity of this solution?
Here's my C++ O(n) space solution:
class Solution {
public:
bool wordBreak(string s, vector& wordDict) {
int n=s.size();
bool dp[n+1];
memset(dp,0,n+1);
dp[0]=1; int end;
for(int start=0;start
thanks Tushar for another great video.
Just to emphasize - The purpose of the problem is to answer if the string can be break into words.
(not like other DP problems where we need to find minimum or maximum cost, etc).
However, it should be mentioned that the optional break, suggested at the end is only one option out of many possible options, that can be discovered if we keep checking for ALL possible break-points in every substring we handle
I think You should mention your dictionary first(Like "mace" also comes in dictionary ) ... else explanation is good !!
what is the string and what is the dictionary ?
how come 'm' is not a word in dictionary but 'a' is ??? Please explain
How many of u r watching in this Lockdown
which dictionary is he referring to?
Thanks Tushar. Can you please explain the time complexity of this approach?
***** Can you explain how it is O(m^3)? Thanks.
Iniyan Paramasivam look at the equation at the end, there is clearly a loop over i, inside which there is a loop over j, and further, inside j, there is a loop over k. so, n^3.
+Tushar Roy
Is this solution with O(m^3) the most efficient algorithm?
What is the time complexity????
mace is a word, pretty good explanation though
thanku so much..i have started liking dynamic prog because of u..
please add recursion tree in your video too...
Is it able to solve this question using 1 dimension array instead of 2 ?
why 'c' and 'e' not in dictionary at the beginning?
because a is an article in english and you can find it in a dictionary and the same applies to I, but not for m ,c,e.
In english, 'A' is an actual word. 'C' and 'E' are just letters of the alphabet.
This can be done in a 1D array of DP instead of 2D DP array.
public class Solution {
public int wordBreak(String s, ArrayList B) {
boolean[] t = new boolean[s.length()+1];
t[0] = true;
Set dict = new HashSet(B);
for(int i=0; i s.length())
continue;
if(t[end]) continue;
if(s.substring(i, end).equals(a)){
t[end] = true;
}
}
}
return t[s.length()] ;
}
}
Brilliant as always. Thanks!
Not optimized DP solution ,can be even further optimized..
you should try to print all possible word breaks not just return true and print only one result..this problem basically belongs to backtracking and recursion..though i appreciate the dp approach
What words are in the dictionary?
What is your dictionary ?
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.
So you are the Fire Fist Ace
New era of interview Programmming channel in youtube :D
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
Bhai board k saamne khade hoge toh kaise dikhega? -_-
Bhai dictionary kaha hai tumhara ?
This is a very good explanation. Thank you for your valuable time.
Can you tell me algorithm of it?
what is the time complexity?
O(n^4) cause string matching will take O(n) and O(n^3) for filling the matrix
where is dictionary ???
why don't you first explain your dp function ?
awesome brother ...
else T[I][J] is false :) in the last line of recurrence relation....very well explained!
Nice explanation.
Very good sir
I,am,a,ace are words in the dictionary
Not properly explained.
where is the dictionary😒😒
one's again Hamshahry let me now "Forbedden" for what?
Hello Sir,
Thank you so much for the videos. Your service is definitely helping thousands of us to secure our dream job.
I have a question about this solution. When I was looking at different approaches for this problem, I came across the below solution,
Map memoized;
String SegmentString(String input, Set dict) {
if (dict.contains(input)) return input;
if (memoized.containsKey(input) {
return memoized.get(input);
}
int len = input.length();
for (int i = 1; i < len; i++) {
String prefix = input.substring(0, i);
if (dict.contains(prefix)) {
String suffix = input.substring(i, len);
String segSuffix = SegmentString(suffix, dict);
if (segSuffix != null) {
memoized.put(input, prefix + " " + segSuffix);
return prefix + " " + segSuffix;
}
}
memoized.put(input, null);
return null;
}
This approach seems to be simple with time complexity of O(n^2). Could you please tell us how your solution differs from this.
This can be solved using 1-D dp.
DP will be the death of me!!
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
Great work
it's 6x6 matrix not 5x5
There is a bug on solution for this video on github on method at line #60 - one line 73 you are subscring too much
Very clear explanation, thank you!
thanks as always!!
Thanks Tushar for the explanation.
bit confusing
You are solving this problem at 0(n^2 ), this is not how DP is used to solve this problem
take a look at this link
www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/
slower soln
You rock man!