i watched almost all of your videos and they really improved my problem solving skills a lot, I don't fear graphs, tries and heaps anymore, Thank you for that.
Although i have solved this problem earlier still i was excited to see this video.. that's the level of your teaching skills..you explain stuffs in a very precise and streamlined manner..Thanks for all your explanations.
@@techdose4u Since you have not given the solution. I have coded it by myself. Can you tell the error it's not working for cases when we can use strings in the dictionary again class Solution { public: bool wordBreak(string s, vector& wordDict) { int n = s.length(); unordered_setm(wordDict.begin(),wordDict.end()); int dp[n][n]; for(int g=0 ;g
Rather than using the substr function, we can push each character at a time into a segmented string initialized with an empty string. This will bring down the complexity to O(n^2)
i didn't get the memoization solution why you are doing i-pos+1 let say if pos is 3 the first substring will now from pos (i.e 3) to (i-pos+1 == 3 - 3 +1 = 1 ) how can be substring end value is smaller than the starting value it will surely give error
Your explanation is always clear and easy to understand. I've learned a lot. :) But... could you please also do binary search problems? It's quite hard to figure out why I need to solve the problem with binary search. For example, Leetcode 774 Minimize Max Distance to Gas Station. I want to know about your thinking process when you encounter hard binary search problems! Anyways thank you always Techdose, I hope you gain more subscribers soon! You deserve more and more.
so sir in the Backtracking approach also we are creating substring every time so should Not the Time complexity be O(2^N * N ) this multiple of N for creating substring every time?? As its is N^2 * N is Dp memoization approach
Brute force, better for loop variable: class Solution { private Set dictSet = new HashSet(); public boolean wordBreak(String s, List wordDict) { for(String str : wordDict) { dictSet.add(str); } return wordBreakRecur(s, 0); } private boolean wordBreakRecur(String s, int pos) { if(pos == s.length()) return true; //whole string has passed. //all substrings starting at 'pos', ending at all possible end and //wordBreakRecur on s from next position of matched word. for(int end = pos + 1; end
Nice video, but I didn't understand one thing: if you are recursively evaluating left and right partition with "&&", then even a single false should cause the entire operation to return false, because true && false is false. So how are we getting true at the end inspite of having few false evaluations in between?
Hi Tech dose I see that the code link is empty. Do you plan to add it as you normally do or it won't be the case for this video. BTW awesome video as usual, thank you very much
Loved you videos on DP. By the way if you get free time for making videos then please make a video on flip the string into monotone increasing leetcode problem I think I need to understand better...Thanks for teaching us these valuable things...
@@techdose4u sure. I am gonna code it according to your explanation. If works, i will add in the comment. Also, as a optimization, we are only concerned about the first row of dp. So we can optimise space complexity.
I don't see how memo helps as the result stored in memo will only be used once (when evaluated) and never be re-used, say there is a valid sentence ilikemango, the call stack is like this wb(i) / \ true wb (like) / \ true wb(mango) / \ true true so where is the memo helping as a cache & preventing recomputation?
DP appraoch code is not working , please check ( java), i have done in java only this part was changed Set set = new HashSet(); for(String word:wordDict){ set.add(word); }
Using a dp array, you could bring down the space complexity from O(n^2) down to O(n). Time complexity remains O(n^3).
Nobody:
Tech dose: uploads at 3:30 AM😂
😂
😅
Whenever i search better solution i always use to check is there any video from @tech dose
:)
Same here
Same
i watched almost all of your videos and they really improved my problem solving skills a lot, I don't fear graphs, tries and heaps anymore, Thank you for that.
but google SDE role test is today
@@yashgandhi9698 so? they've got a thousand interviewer there, pretty sure someone facing some kind of interview each day. LOL
Although i have solved this problem earlier still i was excited to see this video.. that's the level of your teaching skills..you explain stuffs in a very precise and streamlined manner..Thanks for all your explanations.
Great ❤️
Yes he is best in this field till now, always making extra examples and effort to explain. Other youtubers dont give examples
@@techdose4u Since you have not given the solution. I have coded it by myself. Can you tell the error it's not working for cases when we can use strings in the dictionary again
class Solution {
public:
bool wordBreak(string s, vector& wordDict)
{
int n = s.length();
unordered_setm(wordDict.begin(),wordDict.end());
int dp[n][n];
for(int g=0 ;g
Rather than using the substr function, we can push each character at a time into a segmented string initialized with an empty string. This will bring down the complexity to O(n^2)
N^2 log(K) to check in the dictionary
@@abhishekchoudhary5713 UNORDERED SET WOULD BRING DOWN SEARCH TIME TO 0(1)
HENSE 0(N*N)
I understood something from others videos after seeing yours every thing seems to be confusing
wow, loved the explanation and the way you arrived at the most optimal solution. Thanks for the videos, keep them coming :)
I watched your entire DP Playlist. It really helped a lot. Thanks for creating such quality vedios. Hoping for more vedios like this.
Great explanation Sir !! Sir, I think you forgot to attach the code link. Can you plz share it ?
Typo. First approach
s.substr(pos, i+1)
Really nice explanation, it must have taken a lot of efforts and hardwork. Thanks a lot!!
Thanks. Yes it did 😅
Thanks man, best explaination for this question on utube
the best thing is you r focusing on intuition rather than code.
Great. Working even at night
I think he scheduled it at AM instead of PM😂
Yea. Just got time now after my LIVE classes 😅
@@sainathsingineedi2922 it's not scheduled man 😂
i didn't get the memoization solution why you are doing i-pos+1 let say if pos is 3 the first substring will now from pos (i.e 3) to (i-pos+1 ==
3 - 3 +1 = 1 ) how can be substring end value is smaller than the starting value it will surely give error
yes, I was thinking the same. I guess there should be s.substring(pos,i+1)
Your explanation is always clear and easy to understand. I've learned a lot. :) But... could you please also do binary search problems? It's quite hard to figure out why I need to solve the problem with binary search. For example, Leetcode 774 Minimize Max Distance to Gas Station. I want to know about your thinking process when you encounter hard binary search problems! Anyways thank you always Techdose, I hope you gain more subscribers soon! You deserve more and more.
Thanks :)
Noted
so sir in the Backtracking approach also we are creating substring every time so should Not the Time complexity be O(2^N * N ) this multiple of N for creating substring every time?? As its is N^2 * N is Dp memoization approach
Thanks!
Variation of Matrix chain multiplication. Great explanation.
Brute force, better for loop variable:
class Solution {
private Set dictSet = new HashSet();
public boolean wordBreak(String s, List wordDict) {
for(String str : wordDict) {
dictSet.add(str);
}
return wordBreakRecur(s, 0);
}
private boolean wordBreakRecur(String s, int pos) {
if(pos == s.length()) return true; //whole string has passed.
//all substrings starting at 'pos', ending at all possible end and
//wordBreakRecur on s from next position of matched word.
for(int end = pos + 1; end
Most waited solution from you channel bhaiya
Great
s.substr(pos,i-pos+1) is wrong suppose pos = 4 , it will be s.substr(4,1) which will throw index out of bound exception
The DP solution is hard to understand in my opinion. Its much simpler than what it explained.
Thanks sir..i was able to solve it just after 9 minutes watch..it was that great! Thanks a lot
What do you use to write these things clearly. Like what software and what gadget?
Thanks a ton! This was a great explanation!
Great explanation. Thanks
Sir finally you are back....now keep posting videos on regular basis... really appreciate your efforts ❤️
Thanks. I was always there
and why did you create the String t? if you are not using it? at 16:40
18:50 How is time complexity O(N^2) for the recursion after memoization? Can someone please tell.
what is the advantage of using dp here, like we get a o(n^3) solution here , but by using a map i can get an o(nlogn) solution in the average case
how?
23:10 is the time where you will get goose bumps.
Trie solution would probably be trivial but this was ingenious! thanks.
Nice video, but I didn't understand one thing: if you are recursively evaluating left and right partition with "&&", then even a single false should cause the entire operation to return false, because true && false is false. So how are we getting true at the end inspite of having few false evaluations in between?
10:03 why it is 2^N? Each point can have more than 2 branches, so it should be N^N isn't it?
Hi Tech dose I see that the code link is empty. Do you plan to add it as you normally do or it won't be the case for this video.
BTW awesome video as usual, thank you very much
Ohh....I forgot to add. Let me add it now. Thanks for reminding.
Where is the code link?
Thanks
welcome
Bhaiya can you please make video on Word wrap problem also? I am really struggling with it
Sure 👌🏼
Good One!
Thank you sir , good explanation
Great approach bro 🤩🤩🤩
Loved you videos on DP. By the way if you get free time for making videos then please make a video on flip the string into monotone increasing leetcode problem I think I need to understand better...Thanks for teaching us these valuable things...
how did you analyse the time complexity at 16:41
Thanks sir i was waiting for this question ..
Great
in question its mentioned one or more subsrings not all
CAN SOMEBODY TELL ME THE SOFTWARE NAME FOR THIS BLACK SCREEEN.
I guess using a linear dp we can do it in O(n^2) time instead of O(n^3) time complexity.
how are you sure that when pos == s.length, it will be valid string? the whole string also might not be in the dictionary right?
Very much similar to palindrome partitioning
👍🏼
Why do we need String t in the backtracking approach?
please make a video on valid permutations of DI sequence from leetcode dp hard
One day i will try to copy whole your video content and translate into my mother tongue 😀.
what happens to time complexity when we use memorization for n^3 time complexity
Good video. Where's the code link?
Forgot to update 😅
@@techdose4u sir...how to approach these problems...I tend to forget them..please help
class Solution {
public:
bool wordBreak(string s, vector& wordDict) {
setst(wordDict.begin(),wordDict.end());
int n=s.length();
bool dp[n][n];
memset(dp,false,sizeof(dp));
for(int w=0;w
Could you please upload the code for this problem
Why is memoization complexity n^2 ?
where are the code links ?
Hi, can you please make a video on Median in row wise sorted matrix?
how it is a backtracking?
I wish you added the code link
I will add it :)
@@techdose4u sure. I am gonna code it according to your explanation. If works, i will add in the comment.
Also, as a optimization, we are only concerned about the first row of dp. So we can optimise space complexity.
I don't see how memo helps as the result stored in memo will only be used once (when evaluated) and never be re-used, say there is a valid sentence ilikemango, the call stack is like this
wb(i)
/ \
true wb (like)
/ \
true wb(mango)
/ \
true true
so where is the memo helping as a cache & preventing recomputation?
Sir code link?
osssum!!!!!!!!!
Thanks
Sir plz share the code link??
just mcm variation
your intuitive approach fails at this test case
"aaaaaaa"
["aaaa","aaa"] at 7:10
getting index out of bound error
Waiting for DP with Bitmasking !
👍🏼
DP appraoch code is not working , please check ( java), i have done in java
only this part was changed
Set set = new HashSet();
for(String word:wordDict){
set.add(word);
}
code link??
class Solution {
public:
bool wordBreak(string s, vector& wordDict) {
setst(wordDict.begin(),wordDict.end());
int n=s.length();
bool dp[n][n];
memset(dp,false,sizeof(dp));
for(int w=0;w
DP solution could be solved using 1D. You made it complicated by using 2D Array.
❤
but we have to solve qustion in O(N*N) time complaxity anyone give my idea about it🤩🤩🤩
complexity*
@@aayushpagare9366 yes
What if dictionary=["pen", "penny", "wise"] and word is "pennywise"
Rewatch the video :)
Yes I also had this doubt
@@coder1015 first we will choose pen and then will backtrack and choose penny instead ;)
Kya samjhate ho bhai kuch samjh nhi ata jab english acche se nhi ati to hindi me samjaho na yr
worst explanation. You should explain it lil short and crisp. too much information also will confuse.
Noted 👍🏼
Your explanations are tedious, just get to the point man. You repeat obvious things so many times and just prolong it so much it's just annoying.
i do not understand anything by watching this video please everyone don't watch his video because he gives very poor explanation
Worst explanation ever