this is a great explanation, however, how would someone come up with this great algorithm on the spot during the interview? my friend failed an interview, because he didn't know the LCS equation, I guess we should just memorize interview questions at this point
@@orangefield2308 I do understand. I love being able to follow along and think.. WOW that is so clever! I like watching people fill up the DP matrix. But, I sort of feel the same about.. well.. do I have to memorize 10k equations? I dont know.. I do think we have to memorize the process and backing of a lot of these classics .
Thanks so much. Many people just start with a 2D array and some logic. You explained why we need that 2D array and clarified that it is intended for bottom up approach.
For this who did not understand the bottom-up solution : The bottom up approach is similar to the recursive solution we start from n=0, m=0 . The first row and the first column will be 0. From n=1, m=1 we follow this : if P[n] == Q[m] : lcs[n,m] = 1 + lcs[n-1, m-1] else : lcs[n,m] = max(lcs[n-1, m] , lcs[n, m-1]) The thinking behind this is the same as the recursive solution but we are just starting from the first and does not involve multiple function calls on the stack. Hope this makes it clear.
Very nice and clear explanation. After realizing how the recursive solutions works, I didn't have much difficulty to implement iterative version and then apply the same technique to find lcs of 3 strings. The logic for 3d array stays almost the same as for 2d array. Thank you, your video was very helpful!
CS Dojo, great video, I appreciate your work, your explanation actually helped break a mental block and see prefixes and suffixes.. in the bottom up approach, you might have explained a bit more why the value of matching characters in the P and Q strings is the value of the previous diagonal cell plus 1.. I think I now understand that, in the case of bottom up computation, we use suffixes (we look from current position to the end of the string) and if we match 2 characters than we take the result of the previously matched suffixes -- the result would be at location dp[i - 1][j - 1] and increment it by 1.. which is the previous diagonal cell.. Thanks
All this time I dreaded dynamic programming and thought it was some kind of arcane dark art. You made it very intuitive to understand! You. Are. Awesome! Keep the videos coming man!
Hi, this video was very informative, but it would be more helpful if you added links with the code for both the memoization and bottom up approach in the video description.
Using your bottom-top solution and i use the P="AA" and Q="AAB" and the output is 2 (correct), i print the 2d array it looks exact same like what you drawn, but when i input P="BATD" and Q="ABACD". It print out 2, not 3.
Hi, I had the same issue. This was my mistake: * You need your 2D array to be with dimensions p.length()+1 and q.length()+1 So, when you call lcs the first time you pass p, q, 4 and 5 but you check p.charAt(4-1) and q.charAt(5-1) - like in the video (n-1 and m-1). Your final answer is in array[n][m] :) Lmk, if this helps
Can you try this? A = [] B = [] cache = [[0 for x in range(len(B))] for y in range(len(A))] def lcs(a, b, cache): for row in range(0, len(a)): for col in range(0, len(b)): if a[row] == b[col]: cache[row][col] = 1 + max(cache[row-1][col] , cache[row][col-1]) else: cache[row][col] = max(cache[row-1][col] , cache[row][col-1]) return cache[len(a)-1][len(b)-1]
An idea would be to use an hash table with keys in form of (1e3 * N + M) as memoization mean. There only one thing that I don't get: why we don't memoize right after each recursive call?
I especially like the part where you expend the possibility and then optimize the redundancy with DP. I used to watch another video, th-cam.com/video/BysNXJHzCEs/w-d-xo.html, but I realize that jumping to the most optimal solution is not as helpful to fully understand the concepts and make them yours. Please keep bringing the contents like this. :)
It's a great video though, JK! can you please have a general method for DP problems? especially how to approach the problem and which ways can lead to the efficient solutions with several typical problems that have a high frequency in the top-tech interviews. Thanks, JK! PS: I like your explanation, so clear to me though!
Well explained!! But I think the algorithm does not cover all the cases, for e.g. it would fail for P="AAAXAAA" and Q="AXA" try it from left or right. Will appreciate your response!
I feel like this video, while good intention, has a lot of explanations that don't necessarily make things clear. There are some leaps in the explanations that make it hard to follow along, as the reasoning for some of the actions taken while solving the problem.
Hey Dojo. First of all thanks for great video, everything crystal clear except bottom up approach, could you help me with that ? I will really appreciate that. Thanks in advance.
汝之秀，吾何时能及？when can I be as outstanding as you??? seriously, after I got a nice job offer(still a student now), I will share with you, thank you, i'm still waiting for a reply from a nice position, wish me good luck Sugishita san~
excuse me sir, u say that the worst case is 2^(n+m). On the diagram that u drew with n= 2 and m=3, the worst case would be 2^5 = 32. However, when i counted the states by hand they're only 19. please explain? 6:00.
is this method the same as comparing whether the first character of P and first character of Q equal? if they match, recurse with the remaining string besides the first character?
For example, let's say P0 = "abc", Q0 = "cab", the LCS(P0, Q0) should be 3. While LCS(P1, Q0) = LCS("ab", "cab") = 2, and LCS(P0, Q1) = LCS("abc", "ca") = 2, so max(LCS(P1, Q0), LCS(P0, Q1)) will be 2 rather than 3. So I think the equation is wrong.
Actually, I have tried to understand this logic and found out how it works. Suppose last character of P is P[i] and Q is Q[j] and P[i] != Q[j], so LCS never end at i and j together. It could be 2 cases: - LCS end at i - 1 and j if P[i - 1] == Q[j] - LCS end at i and j - 1 if P[i] == Q[j - 1]
At 7:51, shouldn't the time complexity be 2^(max of n and m) instead of 2^(n + m) since technically the depth of the stack cannot go past the length of the strings. Anyone pls feel free to correct me if I am wrong
When in the worst case ,the tree's height is n+m.Try to imagine like that, when start from root, when go to the tree's second level, one of n,m can minus 1, suppose it is m-1, and then go to the third level, it's n's turn to minus-1, and so on...So,the depth of the tree is n+m.
Bottom up approach was pretty bad. I can already see people filling in the table in any resource. But it seems like most people don’t understand the core thought process of filling that table. Fortunately I understood it after seeing this problem a few times.
Yes, It would be the same thing. Just a small change : in the base case you need to use ( n == P.length() or m == Q.length() ) instead of sending n-1 you will send n+1 ..... similarly instead of m-1 send m+1
I am finding it very difficult to visualize. Wish they stop asking these hyper abstract problems in interviews. I know of many people in my company who clear these problems but suck at real world problems. (very badly).
My first attempt to solve this with javascript (ps I didn't see the solution yet): function commonSequence(str1, str2) { var obj = {}; var string = ''; var arr1 = str1.split(''); var arr2 = str2.split(''); var shortLen = arr1.length < arr2.length ? arr1.length : arr2.length; var longLen = arr1.length > arr2.length ? arr1.length : arr2.length; //cache long string characters for(var j=0; j arr2.length ? arr1[j] : arr2[j]; obj[lChar] = 0; } for(var i=0; i
Yes, it is. You are filling up a (n x m)-table, and for each cell, you only perform a constant-time operation on some adjacent squares you have previously filled in. Unfortunately, he only shows how to solve the example with the bottom-up approach rather than presenting a general algorithmic solution, but you can try to think through how each case is based on previous, already computed cases. As I said, his example hints at that.
Not sure why we are using recursion for this problem. Can't we simply do the below solution? def LCS(s1,s2): if len(s1) ==0 or len(s2)==0: return None res = "" for i in s1: if i in s2: res+=(i) s2 = s2.replace(i,"",1) return res # If you need length instead simply do len(res) print LCS('ABACD', 'BATD')
I have a Java implementation of the bottom-up solution here along with some details, if you want to see how it works: github.com/pekoto/PrincetonA/blob/master/PrincetonA/src/com/pekoto/algorithms/LongestCommonSubsequence.java
Simplest explaination I've ever seen of top-down approach. However, I wish the bottom-up method was explained more clearly.
th-cam.com/video/sSno9rV8Rhg/w-d-xo.html
this is a great explanation, however, how would someone come up with this great algorithm on the spot during the interview? my friend failed an interview, because he didn't know the LCS equation, I guess we should just memorize interview questions at this point
@@orangefield2308 I do understand. I love being able to follow along and think.. WOW that is so clever! I like watching people fill up the DP matrix. But, I sort of feel the same about.. well.. do I have to memorize 10k equations? I dont know.. I do think we have to memorize the process and backing of a lot of these classics .
Thanks so much. Many people just start with a 2D array and some logic. You explained why we need that 2D array and clarified that it is intended for bottom up approach.
For this who did not understand the bottom-up solution :
The bottom up approach is similar to the recursive solution
we start from n=0, m=0 . The first row and the first column will be 0. From n=1, m=1 we follow this :
if P[n] == Q[m] :
lcs[n,m] = 1 + lcs[n-1, m-1]
else :
lcs[n,m] = max(lcs[n-1, m] , lcs[n, m-1])
The thinking behind this is the same as the recursive solution but we are just starting from the first and does not involve multiple function calls on the stack. Hope this makes it clear.
Python is so clean and easy on eyes for explaining algorithms. Great explanation and simple!
Oh,My god! Far better than my paid course explanation .Please do more problem solving videos
Very nice and clear explanation. After realizing how the recursive solutions works, I didn't have much difficulty to implement iterative version and then apply the same technique to find lcs of 3 strings. The logic for 3d array stays almost the same as for 2d array. Thank you, your video was very helpful!
This is the best explanation of this problem I have seen. You explanation is great.
CS Dojo, great video, I appreciate your work, your explanation actually helped break a mental block and see prefixes and suffixes.. in the bottom up approach, you might have explained a bit more why the value of matching characters in the P and Q strings is the value of the previous diagonal cell plus 1.. I think I now understand that, in the case of bottom up computation, we use suffixes (we look from current position to the end of the string) and if we match 2 characters than we take the result of the previously matched suffixes -- the result would be at location dp[i - 1][j - 1] and increment it by 1.. which is the previous diagonal cell.. Thanks
Great video, one thing though, it is called Memoization as in (Memo) not Memorization as in Memory.
Here sir has said that we have to memorize the value in memory and the process of storing is called memoization
All this time I dreaded dynamic programming and thought it was some kind of arcane dark art. You made it very intuitive to understand! You. Are. Awesome! Keep the videos coming man!
Thank you for this excellent video. Straight to the point and really well explained.
Omg you also have videos on dynamic programming!!
Thank you so much!!
My brain hurts
th-cam.com/video/sSno9rV8Rhg/w-d-xo.html
Thanks dynamic programming was tough for me. I think now I understand it
The best explanation ever thank you bro
thanks, you actually make it easy to understand
Hi, this video was very informative, but it would be more helpful if you added links with the code for both the memoization and bottom up approach in the video description.
this video was very helpful. thank you
greate video about dynamic programming i have ever seen
Using your bottom-top solution and i use the P="AA" and Q="AAB" and the output is 2 (correct), i print the 2d array it looks exact same like what you drawn, but when i input P="BATD" and Q="ABACD". It print out 2, not 3.
Hi, I had the same issue. This was my mistake:
* You need your 2D array to be with dimensions p.length()+1 and q.length()+1
So, when you call lcs the first time you pass p, q, 4 and 5 but you check p.charAt(4-1) and q.charAt(5-1) - like in the video (n-1 and m-1). Your final answer is in array[n][m] :) Lmk, if this helps
Can you try this?
A = []
B = []
cache = [[0 for x in range(len(B))] for y in range(len(A))]
def lcs(a, b, cache):
for row in range(0, len(a)):
for col in range(0, len(b)):
if a[row] == b[col]:
cache[row][col] = 1 + max(cache[row-1][col] , cache[row][col-1])
else:
cache[row][col] = max(cache[row-1][col] , cache[row][col-1])
return cache[len(a)-1][len(b)-1]
Great Dojo, base condition should be checking with -1!!
Very Good Explanation. Thank You
VERY NICE CONCEPT ABOUT LONGEST COMMOM SUMSEQUENCE STRING
too simple explanation.....this recursive solution explained that formula which is used in DP approach. Thank you!!
This video was so helpful thank so much!!
Nice job explaining the concept.
An idea would be to use an hash table with keys in form of (1e3 * N + M) as memoization mean.
There only one thing that I don't get: why we don't memoize right after each recursive call?
CS Dojo didn't understand the bottom up approach. Would you like to help me out by sharing some resources or making a video?
I especially like the part where you expend the possibility and then optimize the redundancy with DP. I used to watch another video, th-cam.com/video/BysNXJHzCEs/w-d-xo.html, but I realize that jumping to the most optimal solution is not as helpful to fully understand the concepts and make them yours. Please keep bringing the contents like this. :)
Great explanation, Thank you!
You are awesome dear. I really appreciate you. You are helping us. God bless you 😊
great explanation!!
Hi CSDojo, there is a typo mistake at time 7:51...
Line 8th from top... i.e.
Q(n-1) should be replace with Q(m-1).
Same consider with you when I tested
Thank you! Your video helps me so much.
Man, you are soooooo good! Please make more videos. I've subscribed.
It's a great video though, JK! can you please have a general method for DP problems? especially how to approach the problem and which ways can lead to the efficient solutions with several typical problems that have a high frequency in the top-tech interviews. Thanks, JK!
PS: I like your explanation, so clear to me though!
very nice !thanks
The bottom up approach isn't clear. Can you explain in another video please?
Thanks for this great video 👍👍
great job! love your videos ... looking forward for more
Another great video ! Thanks
which of these 3 approaches is best
Great job on this, thank you.
Well explained!!
But I think the algorithm does not cover all the cases, for e.g. it would fail for P="AAAXAAA" and Q="AXA" try it from left or right.
Will appreciate your response!
Recursive solution works for this. Got 3.
Loved it ! Thanks a ton!!
thank you soooooo much!!
it is really helpful
I feel like this video, while good intention, has a lot of explanations that don't necessarily make things clear. There are some leaps in the explanations that make it hard to follow along, as the reasoning for some of the actions taken while solving the problem.
Hey Dojo. First of all thanks for great video, everything crystal clear except bottom up approach, could you help me with that ?
I will really appreciate that.
Thanks in advance.
Please make more videos on dynamic programming
In the memoized solution, shouldn't the arr be arr[n+1][m+1] ?
Great job! Love your videos a lot! :)
汝之秀，吾何时能及？when can I be as outstanding as you??? seriously, after I got a nice job offer(still a student now), I will share with you, thank you, i'm still waiting for a reply from a nice position, wish me good luck Sugishita san~
excuse me sir, u say that the worst case is 2^(n+m). On the diagram that u drew with n= 2 and m=3, the worst case would be 2^5 = 32. However, when i counted the states by hand they're only 19. please explain?
6:00.
There is a mistake in code
P[ n-1 ] != Q[ m -1]
thanks bro
Amazing!
Hi CS Dojo, it's incorrect to call it memorize, its memoized, without the letter R. It comes from the concept of writing something down on a memo pad.
is this method the same as comparing whether the first character of P and first character of Q equal? if they match, recurse with the remaining string besides the first character?
Can someone explain the bottom-up approach?
th-cam.com/video/sSno9rV8Rhg/w-d-xo.html&pbjreload=101
Could you explain why LCS(P0, Q0) = max(LCS(P1, Q0), LCS(P0, Q1)) when last characters are different?
Yeah, I think this equation may not be right, hmm
For example, let's say P0 = "abc", Q0 = "cab", the LCS(P0, Q0) should be 3. While LCS(P1, Q0) = LCS("ab", "cab") = 2, and LCS(P0, Q1) = LCS("abc", "ca") = 2, so max(LCS(P1, Q0), LCS(P0, Q1)) will be 2 rather than 3. So I think the equation is wrong.
@@tinglinliu7476 In your example, LCS(P0, Q0) should be 2 which is "ab". The LCS should from left to right and could be noncontinuous.
@@kevintran6102 Oh, then that makes sense now. I thought it's find the longest common set of characters :)
Actually, I have tried to understand this logic and found out how it works.
Suppose last character of P is P[i] and Q is Q[j] and P[i] != Q[j], so LCS never end at i and j together. It could be 2 cases:
- LCS end at i - 1 and j if P[i - 1] == Q[j]
- LCS end at i and j - 1 if P[i] == Q[j - 1]
We have to take the maximum value between A[n-1][m] and A[n][m-1] if the characters don't match?
This doesn't work apparently my m value I getting negative and there is an error list index out of range.
At 7:51, shouldn't the time complexity be 2^(max of n and m) instead of 2^(n + m) since technically the depth of the stack cannot go past the length of the strings. Anyone pls feel free to correct me if I am wrong
When in the worst case ,the tree's height is n+m.Try to imagine like that, when start from root, when go to the tree's second level, one of n,m can minus 1, suppose it is m-1, and then go to the third level, it's n's turn to minus-1, and so on...So,the depth of the tree is n+m.
Ideally, there should be reduction to using 2 arrays :)
Bottom up approach was pretty bad. I can already see people filling in the table in any resource. But it seems like most people don’t understand the core thought process of filling that table.
Fortunately I understood it after seeing this problem a few times.
sir for me bottom-up method not clear
why do we check the last characters? would it make sense to check the first characters are equal instead of the last one?
Yes, It would be the same thing.
Just a small change :
in the base case you need to use ( n == P.length() or m == Q.length() )
instead of sending n-1 you will send n+1 ..... similarly instead of m-1 send m+1
THANK YOUU
Can you explain it in detail sir
It's hard for me
I am finding it very difficult to visualize. Wish they stop asking these hyper abstract problems in interviews. I know of many people in my company who clear these problems but suck at real world problems. (very badly).
My first attempt to solve this with javascript (ps I didn't see the solution yet):
function commonSequence(str1, str2)
{
var obj = {};
var string = '';
var arr1 = str1.split('');
var arr2 = str2.split('');
var shortLen = arr1.length < arr2.length ? arr1.length : arr2.length;
var longLen = arr1.length > arr2.length ? arr1.length : arr2.length;
//cache long string characters
for(var j=0; j arr2.length ? arr1[j] : arr2[j];
obj[lChar] = 0;
}
for(var i=0; i
PS: I'm using the shortest string to build the sequence. In this case "ABACD" is the shortest therefore the result would be ABCD
Is the running time for bottom up approach the same as Memoization?
Yes, it is. You are filling up a (n x m)-table, and for each cell, you only perform a constant-time operation on some adjacent squares you have previously filled in. Unfortunately, he only shows how to solve the example with the bottom-up approach rather than presenting a general algorithmic solution, but you can try to think through how each case is based on previous, already computed cases. As I said, his example hints at that.
I get a syntactical error in Python on the first "else if" statement, no idea why.
else if ------> elif (in python)
But how to find the long common subsequence. I mean the string. This algorithm is to find the max length.
Just take a string and add the char to string everytime you increase result.. finally reverse the string
What is the use of this?
I am sure everyone knows this.. but memorize... actually is memoize
Letting u know
brillant
Dude, what happend. 0:27 - You have underlined alphabets wrong.
Not sure why we are using recursion for this problem. Can't we simply do the below solution?
def LCS(s1,s2):
if len(s1) ==0 or len(s2)==0:
return None
res = ""
for i in s1:
if i in s2:
res+=(i)
s2 = s2.replace(i,"",1)
return res # If you need length instead simply do len(res)
print LCS('ABACD', 'BATD')
Your solution would return ABD which is not a subsequence. BAD is a subsequence. Your solution returns the common characters in the two strings.
Can you do this iteratively?
Yes we can do it iteratively but it takes O( n*m)
I have a Java implementation of the bottom-up solution here along with some details, if you want to see how it works:
github.com/pekoto/PrincetonA/blob/master/PrincetonA/src/com/pekoto/algorithms/LongestCommonSubsequence.java
Watch this video to learn how to solve variation of lcs:
th-cam.com/video/cPuQqNUg8iQ/w-d-xo.html
This video has errors on bottom-up approach. Watch this instead: th-cam.com/video/sSno9rV8Rhg/w-d-xo.html
ChatGPT solves problems involving LCS and others in 5-10 seconds for me. Programming is dying.
Memoize, not memorize
ngio' capito n cazz
It's "memoize," not "memorize."
awesome explanation!!!
Can you explain it in detail sir
It's hard for me
Can you explain it in detail sir
It's hard for me