Interleaving String | Dynamic Programming | Leetcode #97
Vložit
- čas přidán 12. 11. 2020
- This video explains a very important programming interview problem which is to find if a given string is an interleaving string of two other strings.I have explained the intuition for solving this problem along with all the required analysis and observations.I have first explained the problem statement using good example and then i have shown the intuition for solution using proper observations.I have also shown the requirement analysis of the problem and then I have shown the simple recursion solution.Recursion solution is exponential, therefore I have also shown the optimization to solve using the top-down dynamic programming approach which is also known as memoization.The time complexity reduces from exponential to polynomial.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL VIDEOS:-
Unique Paths: • Unique Paths | Dynamic...
Uncrossed Lines: • Uncrossed Lines | Dyna...
Count Square Submatrices: • Count Square Submatric...
#dp #topdown #memoization
Having Knowledge is different and the ability to deliver it at its best is different. And You have both!
Thanks
You deserve an award. Thank you for your videos.
Welcome 🤗
Your channel is the best . No other channel gives such a crystal clear explanation. 💯
Thanks :)
if one of the strings is finished which you check starting on line 12, you can directly check the remaining of s3 with the remaining of the other string. no need for recursion calls. And also you can early exit if the calls starting from line 19 is true, no need to continue to call the other, since we have found a solution.
so much energy invested for us . Thanks for these quality contents!
Knowing how to solve a problem is one thing, being is able to breakdown the solution in digestible manner is a whole different ball game. You explanations are top notch! Thank you for visualizing the recursive call and drawing out the solution. This was super helpful
Your efforts are worth appreciation !!
Thanks :)
Your explanation was the best for this problem...compared to other videos❤
best explanation at all, thanks for these quality contents!
Thank you sir. Your explanations are always very helpful!
Welcome
Thank you for the great explanation.
If p3 is equal to len3, we can return true without checking p1/p2 because we have made sure that number of characters in s3 is equal to sum of characters in s1 and s2.
We can also choose key in HashMap as "i+"*"+j"
When i look at the DP questions it seems tough and very difficult how to break it down ,but the way you make it happen is really cool !!!
very clear explanation so much energy invested for us viewers to understand correctly. thank you
Welcome :)
Your efforts are visible, Thanks !!
Always loved your explanation :)
It's getting harder and harder Surya. I wanna cry 😭😭😭😭
It was always hard from the very beginning. You will get better believe me 🤗
That's what she said
don't worry keep practicing and never give up and never underestimate or overestimate your self you will succeed .
Thank you for this amazing solution. I only have one confusion - how did you calculate the time complexity after optimization.
amazing ,one of the best explanation I have ever seen !
the concept u explained is little difficult to grasp. I have simplied the concept and written the code. 0ms java accepted code on leetcode.
class Solution {
int m, n;
char[] X;
char[] Y;
char[] Z;
Boolean[][] mem;
public boolean isInterleave(String s1, String s2, String s3) {
m = s1.length();
n = s2.length();
int l = s3.length();
if(m+n!=l) return false;
X = s1.toCharArray();
Y = s2.toCharArray();
Z = s3.toCharArray();
mem = new Boolean[m+1][n+1];
return check(0,0);
}
boolean check(int i, int j){
//base case
if(i==m && j==n) return true;
// memoization
if(mem[i][j]!=null) return mem[i][j];
// if X is exhausted
if(i==m)
return mem[i][j] = Y[j]==Z[i+j] && check(i,j+1);
// if Y is exhausted
if(j==n)
return mem[i][j] = X[i]==Z[i+j] && check(i+1,j);
//try both combination
return mem[i][j] =(X[i]==Z[i+j] && check(i+1,j)) || (Y[j]==Z[i+j] && check(i,j+1));
}
}
please give the example of previous state calculation that used in current state or why it is solved using Memoization?
mention overlappaing property.
Other than that every thing is good!!!!!
sir ur explaination is so awesome kindly request to you please sir create playlist for some important data structure and also codeforce and codecef contest explanation, contest explaination would be more helpful for us please sir
Could you please also explain the 2D dp array approach, like how one solution is coming from the solutions of 2 sub problems.
Thanks for the explanation. Can we take 3 pointers approach also, will take m+n time complexity?
Great explanation. I don't think checking for p1 == len1 && p2 == len2 is needed in base case, just return true. By the time p3 == len3, interleaving condition is satisfied and p1,p2 will reach end of the respective strings. Since we did already have length check in isInterleave().
I would say that recursive solution can be simplified e.g. cases 1 and 2 are covered by case 3 either way. Therefore, they can be removed from code.
Wissing you happy diwali sir .god bless you . Ese hi students ki help karte rahein 😅
Thanks :) Wish you the same.
for this problem in leetcode, using your code it showing the time limit exceeded. is there any other better and faster solution?
Beautifully explained
What's the point of memoization in this problem? When would you end up checking the map and finding the same key? How would you even end up checking the same path twice?
he has not expained this part, i.e, how the subproblems are repeating
Great explanation thanks !!
Thank you so much for this video! I have a quick question though, why is the number of unique keys == m * n, and not m * n * length of string s3?
M*N covers all the ranges of keys. Doesn't it ?
I am also getting confused in this.
m*n covers all possibilities and its not wrong to take m*n*k also ..
Can this be solved by dp table method like knapsack?
Excellent explanation, to the points.
Thanks
shouldn't we merge both strings a and b, then sort both resultant and c and compare.
Good Explanation!!!
What is the optimized time complexity?
once you fix p1 and p2 , p3 automatically gets fixed then why are you putting this in state
Clearly understand..
Thanks! Nice Explanation!
Welcome :)
Could you solve it in linear space?
can you please run through the below input in sliding pointer technique, s1 = "aabcc" , s2="bccba" , s3 = "aabccbcbac".
in the recursive solution how do we know that s3 is following interleaving pattern s1+t1+s2+t2...
I told in the video that you just need to check for order of substrings. First of all, mod(N-M)
@@techdose4u so we only need to check the order
Very Nice Explanation
Thanks :)
Great solution. Note, p3 is not required to be a part of the cache key.
👍🏼
Thank you! Wish you a Very Happy Diwali.
Welcome 😃 same to you
Hi,Just asking that will it work for empty string case also?
Dint check
There is no need to write
if(p1==len1)
return mem[key] = s2[p2]==s3[p3]? check(s1,s2,s3,len1,len2,len3,p1,p2+1,p3+1):false;
if(p2==len2)
return mem[key] = s1[p1]==s3[p3]? check(s1,s2,s3,len1,len2,len3,p1+1,p2,p3+1):false;
Because we checking these conditions with bool one and two
In the bool one and two conditions ,we're only checking whether chars are matching or not if don't have this check of length then we would get run-time error of accessing location s1[len1]
We can upsolve this using bfs too
Hey bro ,I have a doubt can we use n*m dp array then get to all the cases and store all the cases and I think if condition where (p1 == len(s1) ) and ( p2 == len(s2) ) is not required,pls reply.
i also think ur way !! but not sure abt it.
@@Yash-uk8ib I have solved it that way now,it worked.
Oh thats nice, i am actually bad at iterative dp, thanks for informing sir, appreciated
the solution on submit gave error. Kindly check your solution and submit. Pls make the updated video.
Did you have DP version of code for this?
Here is the dp code in javascript version executed successfully in leetcode.
/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
var isInterleave = function(s1, s2, s3) {
const dp = [];
const s1Len = s1.length, s2Len = s2.length, s3Len = s3.length;
if (s3Len !== s1Len + s2Len) {
return false;
}
for(let i=0; i
Awsum:)
😊
Op explained
you should clear the global map at the starting as it will be used again
But that might be used with a different class object. If that's the case then no need to clear.
Sir, I still didn't understand that how overlapping subproblems are discovered, if key is different for every subproblem, how could memoisation works?. I'm very weak in these concepts if question doesn't make sense I'm sorry but nice content!
Actually key will be different for different states which I took combining p1 p2 and p3. Please look at my example in the video, where I took different values still key was same. You can watch the rod cutting problem and apply the same concept of repeating subproblems and optimal substructure. I don't say these basic steps everytime 😅
@@techdose4u yeah sir my question is that if keys are different, memoisation needs repeating subproblems and so keys should happen to be same at some point to overcome recomputation but here keys are different then there will be no recomputation that's my understanding, plz correct me if I'm wrong. If I'm right please explain that subproblems if u have time! I watched the rod cutting but still unable to understand optimal structure for this specific problem. Thanks sir!
@@ayyappahemanth7134 Same query
@@techdose4u If all the keys that will form are unique then what is the use of map we will have no chance to check for any recomputation i don't know if it is benefiting or not kindly explain .
Putting * technique to make key pair unique was best....
I spent like 1.5 hrs to get to the solution but all efforts in vain. Now watching your video to understand it. If these questions are asked in interview then I'm doomed.
nice
Great explanation, Thank you.
I think when s1 and s2 length are same and s3 length is more than s1+s2 it will give index out of bound exception. need to handle p1==len1&&p2==len2 => return false;
s3 will not exceed s1+s2 that condition has already been checked
I wanted to see tabulation method ..
No worries. You can derive the intuition using memoization code.
❤️Tech🔥💻🔥Dose❤️
:)
I can see that this question was tagged as hard at the making of this video. However, they changed it to medium now.
actual explaination starts from 13:32
This came in Microsoft yesterday
we can ignore p3, since p3 will always be p1+p2.
time complexity of recursion + memoization should be O(s1.length() * s2.length() * s3.length()) correct me if i am wrong ??????????????????
right
Hi bro. A small clarification, when creating a key, it is not needed to include p3, because for the given combination of p1 and p2, p3 will always be p1+p2. Correct me if I am wrong.
This is now putted in medium category 😑
:o
class Solution {
public:
int len1,len2,len3;
vector dp;
// dp[i][j] = -1; // yet to be decided
// dp[i][j] = 1; // upto s1[i] and s2[j], is Interleave
// dp[i][j] = 0; // upto s1[i] and s2[j], is not Interleave
bool check(string &s1,string &s2,string &s3,int p1,int p2,int p3){
if(p3==len3)
return true;
if(dp[p1][p2] != -1)
return dp[p1][p2];
bool way1 = false, way2 = false;
if(p1 != len1)
way1 = s1[p1]==s3[p3] && check(s1,s2,s3,p1+1,p2,p3+1);
if(p2 != len2)
way2 = s2[p2]==s3[p3] && check(s1,s2,s3,p1,p2+1,p3+1);
return dp[p1][p2] = (way1 || way2);
}
bool isInterleave(string s1, string s2, string s3){
len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
dp = vector(len1+1,vector(len2+1,-1));
if(len3 != len1+len2)
return false;
return check(s1,s2,s3,0,0,0);
}
};
Little complex to understand
Try to solve by yourself first... Then it must be easier to understand here!!
Recursive Solution which gives TLE:
class Solution {
public:
bool helper(string &s1,string &s2,string &s3,int idx1,int idx2,int idx3){
if((idx1==s1.length() && idx2==s2.length()) && idx3==s3.length())return true;
if(idx1>s1.length() || idx2>s2.length() || idx3>s3.length())return false;
bool ans=false;
if(s3[idx3]==s1[idx1] && s3[idx3]==s2[idx2]){
ans|=helper(s1,s2,s3,idx1+1,idx2,idx3+1)|helper(s1,s2,s3,idx1,idx2+1,idx3+1);
}
else if(s3[idx3]==s1[idx1]){
ans|=helper(s1,s2,s3,idx1+1,idx2,idx3+1);
}
else if(s3[idx3]==s2[idx2]){
ans|=helper(s1,s2,s3,idx1,idx2+1,idx3+1);
}
return ans;
}
bool isInterleave(string s1, string s2, string s3) {
if(s1.length()+s2.length()!=s3.length())return false;
return helper(s1,s2,s3,0,0,0);
}
};
Solution using DP using map
class Solution {
public:
unordered_mapm;
bool helper(string &s1,string &s2, string &s3,int &len1,int &len2,int &len3,int p1,int p2,int p3){
if(p3==len3)return (p1==len1 && p2==len2);
string key=to_string(p1)+'*'+to_string(p2)+'*'+to_string(p3);
if(m.find(key)!=m.end())return m[key];
if(p1==len1)
return m[key]=s2[p2]==s3[p3]? helper(s1,s2,s3,len1,len2,len3,p1,p2+1,p3+1) : false;
if(p2==len2)
return m[key]=s1[p1]==s3[p3]? helper(s1,s2,s3,len1,len2,len3,p1+1,p2,p3+1) : false;
bool one=false,two=false;
if(s1[p1]==s3[p3])one=helper(s1,s2,s3,len1,len2,len3,p1+1,p2,p3+1);
if(s2[p2]==s3[p3])two=helper(s1,s2,s3,len1,len2,len3,p1,p2+1,p3+1);
return m[key]=one|two;
}
bool isInterleave(string s1, string s2, string s3) {
int len1=s1.length();
int len2=s2.length();
int len3=s3.length();
return helper(s1,s2,s3,len1,len2,len3,0,0,0);
}
};
It's taxing to watch such long videos, there are over 1800 problems in leetcode, you can do the math. I think 10 mins should be max for any video, no matter how tough the concept may be, else it's just waste of time, just my opinon!
I won't make all videos. According to your suggestion nobody will understand :) As I keep mentioning, don't count your problems, See how much you learned from a problem :)
@@techdose4u absolutely right brother keep what you are doing cause you are doing it great
@@pranjalbajpai156 thanks :)
I think few dramatic problems like these need more explanation than just 10mins where you need to explain the scenarios, walk through the code and dry run the test cases.
I think 30mins is good as it explains lot of techniques and solves an LC hard
hello any girls here:)
Great explanation thanks !!