Longest common subsequence | Leetcode
Vložit
- čas přidán 27. 11. 2019
- This video shows how to solve the longest common subsequence problem efficiently. This is a famous question of dynamic programming which is frequently asked in programming interviews. I have explained each step in detail with proper reasoning. This question has also come in day 26 of april coding challenge 2020 on leetcode. 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 :)
CODE LINK: drive.google.com/open?id=1Rky...
I had no knowledge of Algo and DS 2 months ago, its within these two months I have learnt all algo and ds related stuff. But this wouldn't have happened without you Algo Buddy. I am very lucky to find a great teacher like you early in my learning journey. THANKS ALGO BUDDY
Great ❤️ keep learning
Oh this channel's name was Algo Buddy, and now it's Tech Dose. Wow!
@@arindam1249 No, it was a name that I gave him 😃
After watching about 8 to 10 videos on youtube, this is the only video which I could vouch to have the exact explanation on why this algo actually works.
Edited: Just make sure that you watch this video atleast 2 times to grasp all the subtle info present inside different layers here.
Thanks bro. ..you are correct. There are many subtle points.
Solving such problems needs the knack of cracking the sub-problems . Thanks for this gem ! Appreciated !
Welcome :)
I was trying to figure out a homework for hours. I watched this video and finished it in less than 3 minutes lol. You deserve a like, really appreciate it.
Nice 😊
man you deserve more subscriber than erichito.I mean he is good in programming himself but not not good at teaching.But you are just brilliant teaching.
😅Thanks
I went through Leetcode official solution which was awesome but didn't explain exactly how the dynamic programming algo works, then watched couple of YT videos. They also missed the reasoning behind it. This is the only video that goes to explain that! Superb.
Thanks :)
Your videos are too good . Thank you so much for keeping it clear to the point and stepwise- recursion, memoization,tabulation. I finally decided to watch your playlist than any other youtube dp playlist :)
Really nice, mentioning reason for each line of code is key points of u r videos. Keep it up
I bow down towards you explanation , I really loved it!!!!
appreciate your work. i like the way you form the longest common subsequence string
Such great explanation!....You explain everything with amazing clearity!
finally Some good content on the CZcams, cheers @TECH DOSE
Thanks bro :)
@@techdose4u Sir ..please do video for longest repeating subsequence..
I have subscribed to you man. Loving your explanations.
Great ❤️
Thank you very much sir for such intuitive explanation, best video i have come across over youtube
Thanks :)
couldn't have gotten a better expalination than this thanks.
Welcome :)
I find this tutorial very helpful, thank you for awesome explanation.
bhagya dharti ke hamare jo tumhare pagg padhare.thnx bhai .great content
😅 welcome
Awesome explanation... your videos are of immense help to lot of coders like us. Please Keep doing this awesome work.
Thanks 😊
Best Explanation !!! Thank you!!
Awesome Explanation!
Thanks sir.your all content are really great. Only because of u i am able to learn ds algo efficiently. Now i am not afraid of programming .keep it up🙏🙏🙏🙏🙏
Nice :)
The best explanation ever !!
Great explanation....
you hit the nail on the head, well done 👏
Thanks ☺️
thanks for awesome explanation
Wow !! Great Explanations buddy.
Thanks :)
Hi Thanks for the crisp explanation. Thanks much. I just have a query. Instead of traversing diagonally to get the string in a reverse fashion, i found it easier to traverse backwards in the last row and record the column where the value shifts/ alter. As always your videos always are a learning experience.
@TECH DOSE thank you! keep making this videos.
Welcome. Sure I will.
Thanks men your explanations are very good.
Welcome :)
you made it look so easy, great work.
Thanks :)
Best explaination that I could find.
Thanks :)
You are awesome sir!
bro u rocked it ......
You are explanation methods are really great sir 🙌🔥.
Thanks 😊
thanks great explanation
very nicely explained!! thank you sir..
Welcome :)
Thanks a lot sir for crystal clean explanation,😍
Welcome
You have great explanation skills.
Thank you for the code.
could you please provide the function to get the "common-string" as 15:10?
👍🏼
best explanation
Beautiful explanation
Explanations made easier 👍
Thanks :)
Very good explanation sir 👍👌
Thanks :)
thanks for your effort 😀
Welcome :)
You the best, regarding the time complexity if we have different lengths for the strings it should be O(N*M) right ?
Yes correct.
It can be done with 2 nested loops right?that the easier and i think thats a brute force approach too
Thank you so much
Welcome :)
Great Great Great❤❤❤
Thanks thanks thanks ❤️❤️❤️
Rather than moving along the table to extract subsequence "ADH" can we instead keep appending the characters in string as and when common match is found between both the strings. I mean to say in below condition of code:-
if (X[i - 1] == Y[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;
for example we can add it in a set and sort it while printing. Please correct me if am wrong here.
You can do that.
This playlist is like bible for DP .
❤️
In order to find out the subsequence itself , can we add that char to a list when we pick from diagonal element ?
Instead you can use a string vector of string as your LIS array. Compare length of string. This can help you keep the string as well.
What if we do like this
int main()
{
std::string s1 = "ABCDGH";
std::string s2 = "ABDFHR";
std::string ans;
std::sort(s1.begin(), s1.end());
std::sort(s2.begin(), s2.end());
auto it = std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(ans));
std::cout
very nice
Sir can you please make a video on Google Kickstart Round C 2020 ,stable wall
Can you post how exactly to convert a memoization solution to tabulation solution?
very good explanation but pls dont do that much ads in the middle of an important explanation. Stops and breaks learning flow :((
Beautiful
why dint you take 2 strings with atleast 1 repeating character?
good explanation sir,
you told that cp and dsa are differet thing, why???
if so , than which is more important to get into product based companies?
if dsa is more important than cp than what is the best resource or platform or book to learn dsa?
please give ans of all these questions sir,
DSA is the primary thing that every programmer should know. For CP, you should know good maths probability series Fourier etc etc with mathematical tricks to reduce effective number of operations. CP is just like a game of puzzle where you need good observation skills to solve a problem. Even if you solve, you need to beat others in time and space as well. DSA focuses on how will you solve a given problem. Which algo to use and which DS to use. The choice may vary from developer to developer. It is not like a game or puzzle or sport. You will not get hidden tricks. Just DS and ALGO will do the work. DSA is most important for product based company. Do you really think everyone working in product based companies are good in CP? Well if you think so then you will be disappointed to know that's it's not true.
Best resource for DSA starters is DS an ALGO by Narsimha Karumanchi and if you are not a beginner then study from geeksforgeeks and leetcode. That's all
@@techdose4u thank you sir for these resources 🤩
@@techdose4u in CZcams there are many videos on cracking interview of google , Gs, Amazon etc and in all videos they says that first step is cp and all those students are saying that either they are pink or red coder on codeforces or they have 5 or 6 in codechef . All they recommend cp to crack interview because all companies have 1 or 2 rounds on coding and then interview
And that's why I asked you to clarify
About cp .
It's not true. If you are good in CP then you will obviously do well in DSA but if you are not good at CP, then also you can do well in DSA and crack interviews. I never did CP myself. But I can say this. If your focus is interview then don't bother about CP. That's my own experience.
Bro I am finding DP very hard to learn. Please tell me the best resource for it.
Best resource for DP is to practice recursion and then read a lot of articles on dp. Only practice can help you.
@@techdose4u I am good at recursion. But I am not able to apply top down approach but I can apply memoisation.
Memoization is optimized recursion. But if you want to convert soln to table format then you need to analyze the recursive formula. You will get this if you practice more and more questions.
Sir,Can you give us the code for printing the Longest common sub sequence after filling the dp table
May be you can backtrack and print using the table starting from last row and last column.
@@techdose4u Sir can you please make a video on Google Kickstart Round C 2020 ,stable wall
what if the two strings have different length/
It will still work. Try it
hi thanks for the sharing solution video. But when it comes to if statement in "formula", shouldn't it be if(s1[i] == s2[j])? not i-1 and j-1. thank you in advance.
I think I was using size of array as N+1 by M+1. So 1st row and col are all zeroes. Therefore, row 1 means first element which is 1-1= index 0.
thnx had the same doubt
I can solve it in nlogn
Can you explain the code walkthrough of this, I understand the concept but not able to crack code on second part collecting the common subsequence.
def lcs_algo(S1, S2, m, n):
L = [[0 for x in range(n+1)] for x in range(m+1)]
# Building the mtrix in bottom-up way
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
L[i][j] = 0
elif S1[i-1] == S2[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
index = L[m][n]
lcs_algo = [""] * (index+1)
lcs_algo[index] = ""
i = m
j = n
while i > 0 and j > 0:
if S1[i-1] == S2[j-1]:
lcs_algo[index-1] = S1[i-1]
i -= 1
j -= 1
index -= 1
elif L[i-1][j] > L[i][j-1]:
i -= 1
else:
j -= 1
# Printing the sub sequences
print("S1 : " + S1 + "
S2 : " + S2)
print("LCS: " + "".join(lcs_algo))
S1 = "ACADB"
S2 = "CBDA"
m = len(S1)
n = len(S2)
lcs_algo(S1, S2, m, n)
your 'E' looks like 'B'
hii i was thinking about this solution
that we can solve it by frequency counting in both the string
and then return number of common characters in both the string .
will it give right answer? please replay.
no,may be the order of both strings are different,for eg ,let consider two string s1=abc,s2=acb,from your approach the lcs would be 3,but actual answe is 2 ,i.e ac.
Everything was going fine, until he refused to show the code!
I already wrote the code on slides. So, it must be easy to code now 😅
@@techdose4u yeah but that does not build the sequence but just returns a value. It would be great if u share that code as well!!
Worst explanation. Ideally one should explain intuition and solution. you are like lets do this and you will realize why we did this. Why the heck one would even imagine at the first place?
I do not get it. You write B, but pronounce E.
Must have been by mistake 😅 I hope you understood what I was trying to state.
@@techdose4u Starting from 5:30 I lost thought ("E and E are not matching") and everything follows sounds like Chinese to me.
@@evgeni-nabokov this is simple only. If we find mismatch in elements then we can skip over the current character from either string 1 or string 2 because we need subsequence. So, we have 2 possible decisions at this given point and we need to take the optimal one. In backtracking we try both but in dp, we will use table for this to decide in O(1) about whether to leave A or E. Where are you getting confused?
Actually, this is not the right way of teaching first you should explain why you choose dp in first place why can't this can be solved using DP, I can say you first go ahead with recursion and analyze dp properties such as subproblems and optimal substructure based on that improvise the solution using memoization and then go for tabulation later you can see when can you optimize time&space please explain intuition before proceeding to dp.