Longest Common Subsequence Dynamic Programming | Explanation with Code
Вставка
- Опубліковано 14 вер 2020
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we discuss the Longest Common Subsequence problem using dynamic programming. In this problem,
1. You are given a string str1.
2. You are given another string str2.
3. You are required to print the length of longest common subsequence of two strings.
To attempt and submit this question, click here: www.pepcoding.com/resources/d...
For a better experience and more exercises, VISIT: www.pepcoding.com/resources/o...
#dp #lcs #dynamicprogramming
Have a look at our result: www.pepcoding.com/placements
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
Sumeet Sir, Just Wow. I have not seen anyone explaining in such great length on the why of the solution to this problem. You are taking India's IT generation to next level and future is not far where lot many inventions and enterpreneurs can be foreseen using this type of education. Dil se Dhanyawaad, great wishes, happiness, peaceful life to you. thank you so much.
pleasure is all mine.
and for better experience, visit nados.io, where you will get well curated content and career opportunities
I saw another video of this problem of another guy where he started with the table that this video reached after 25 minutes of explanation. In that video, I understood nothing how the table was filled while in this one I did not need to watch further and could fill the table myself. Great explanation, totally worth were the 25 minutes.
What an explanation! Nobody explains the algo how it is made just provides them so that we can mug it. Perfect explanation thanks a ton
Great Explanation, I can bet that no one could explain this, better than you , after getting your explanation i never needed to see code , saved this for future reference, thanks Sumeet sir for such a wonderful video .
No words to appreciate, just amazing Thank you very much
Thanks a lot sir for explaining the problem in this much depth.This is the best explanation on LCS.
The best explanation on LCS. Thanks a lot.
Glad to know that you liked the content and thank you for appreciating. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
This guy is explaining at another level
Sir aap agar developer hote toh abhi mast bhar kahi PM rehte . But you chose teaching! Hats off
if there is any video of pepcoding of any question then it is best
you are the beest sir
such an amazing explanation
keep making such videos sir
One of the best explanations on LCS.
Glad you love the explanation, for better experience and well curated content sign up on nados.io and start learning.
Side pe samjhane wala idea mast tha! ☺️
Enjoy your explaining! Thanks a lot!
sir your are legend no words every word fall short for you just love you:)
Glad to know, that you love Team Pepcoding, for better experience and precisely arranged videos.
Visit - nados.pepcoding.com and sign up to NADOS.
Don't forget to follow us on Instagram instagram.com/pepcoding/
i don't know why this channel is so underrated .....
keep motivating, keep learning and keep loving Pepcoding😊
Sir itni mathematics ke wajah se kaafi confusion hogya h aur confidence low ho rha h.. like how can we come up with this deep maths behind a question?
I think sir yeh question ke liye pehle recursive solution fir wahan se DP ka solution wala explanation jyaada sahi rehta..
i think in every dp questio sir should have first expalin us recursive approach
waohh great!! explanation sir
Thank you sir for this beautiful explanation sir , it helps a lot to remember the method when someone explains so deeply to us
you all probably dont give a shit but does someone know of a tool to get back into an Instagram account?
I stupidly forgot my account password. I would love any assistance you can offer me!
Great explanation ❤️
Great work Sir .I'm amazed with your style and content......though I am not a paid student but there is no difference I think between two...🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌.
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Commendable job....... please make a video on Shortest Common Supersequence...
This is best explanation. I have to come here again for understanding many other subsequences questions. 🙏
Glad to hear that. Keep watching and keep supporting Pepcoding😊
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Nice . Liked your video 👌
Hello Sir ..For the same input if we have array of string instead of two string , can we deduce the formula in general
sir ye series thodi shuffled hai, please isko order mei arrange kardo, flow bana rehta hai concepts and learning ka . Thanks!
Awesome explanation sir
Glad that you liked the content and thank you for appreciating beta. I also hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Keep motivating, keep learning and keep loving Pepcoding😊
thanks
sir yahan tak phonchte phonchte ab maza aane laga hai dp mein, naye naye sawal bhi banne lage hain, thank u sir, and here comes a fact "east ho ya west sumeet sir is the best"
keep motivating, keep learning and keep loving Pepcoding😊
Very Nice Explanation......Keep making videos
Thank you, I will and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
sir hum kuchh bar dp left corner se right corner bharte haij kuch time me ulta
better hota agar hum left corner se right corner bharen har baar>>>>
keep up the good work
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Great Explanation the mathematics is too good
Longest Distinct Palindromic Sequence dekhiega
understood
hi sir
Can you please make a video on the Longest Common Subsequence of 3 Strings
Not able to see the proper playlist which was there previously..
i was confused on how recursive sol could be derived from brute force of 2 ^ (n+m) and could not think of it from one day but now it seems total clear, thank you. Also would like to know how you developed this awesome clarity , any book recommendations or mathematics course?
Glad I could help! keep motivating, keep learning and keep loving Pepcoding😊
@@Pepcoding book or course recommendation ?
Might he developed this skill of getting so deep into logic by practicing too much of dsa and making a mixture of all mathematical concepts (khichdi) and evolving a best solution explanation from it.
@@lucky_raiser his math is really clear.
Thanku sir
Keep learning and keep growing😊
If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Can we also start filling this table from top left corner?
How do we identify that this problem needs to be resolved by MCM?? Please suggest
Hello...first of all thank you for your wonderful videos...it is really helpful..
In the website,there is some problem in the compiler ... whenever I submit a solution for the first time it gives me compilation error and after that when I submit the same solution as before it gets accepted(C++)
kra rhe hain beta theik.
Kaha thee guru aap ❤️
How many questions are left in level up as a whole sir( apart from dp)? .please tell the topics and tentatively what is that finishing date? Thanks
Asking as per todays date (5 Nov 2020)
total around 500 rehte hain. dec 31 the new target
maze aa gaye..
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like my efforts, I request a review
g.page/Pepcoding/review?rc
@@Pepcoding kar diya sir review :)
Sir agr srf length hi btaaani hai longest common subsequence ki to hm do hashmap bhi to bnaa skte hai dono string ke liye or character ki frequency store krte hai.
fr ek loop lgaa kr dekh lenge agr wo char ki frequency dono me greater than 0 hai to counter ko bdhaa lenge or end me print krdenge
nhi work kregi kya sr ye approach?
haan aise bhi kar sakte hain , par yahan hum DP padh rahe hain to uski insight ban ni important hai.
This approach is not correct. For example if we take strings: adbc and aebd, your approach will give answer 3 whereas correct answer is 2(ab)
bhai subsequence find krni hai , largest common permutation subset nhi , order matter krta hai
Nope. Tumhari se permutation aa jayegi. Sequence matter karti hai warna Palindrome wali sarii question easy na ho jaati? LMAO
good yar awesome
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like my efforts, I request a review
g.page/Pepcoding/review?rc
@@Pepcoding did it...
Rated 5 stars
29/79 Done
Keep learning and keep supporting us.
And for better experience and curated content sign refer to nados.io
Sir, I really request you to make a video for students in 7th sem, and cover every student (whether his preparation level is 20 percent or he has just started)
TRUST ME, THIS IS THE MOST WATCHED VIDEO ON CODING BLOCKS CHANNEL, and unfortunately that video is not worth
watching..:/
Sir, please consider this..and try to make a video on it asap..
Because we need you the most..this time..
How will we strategise our preparation..
Only you can help
if string containing space then how to handle space. e.g "abdc def"
Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.
If you treat "space" as a character, then the algorithm should remain same. No character would match with it so it would not be considered in the LCS.
Sir stack, queue and LinkedList ka syllabus foundation jitna hi hai, ya abhi usko revisit karenge hum level2 mein, because almost 80% of problems which i have seen in interviews are already covered in foundation??
stack-queue to majorly ho gai thi. linkedlist mei kaafi bacha hai. revisit karke honge.
bhaari sawal
kaise lga sawal? Mza aaya krne main?
@@Pepcoding yes sir
@@Pepcoding sir haalt kharab hogayi thi , soch ne mei. DP ne dara rakha hai buri tarike se.
sir what will be the time complexicity
s1.length*s2.length..jo matrix ka size h whi h complexity.
this is almost LIS
28:22 Can anyone explain how did this come
watch the video from first again ... you will find it out.
Sir Main aapse poore man se pdhna chahtahun par dikkat yh h ki aaap code krte ho java main aur whn mujhe dikkat hone lgti hai Main C/C++ main Smjh pata hu aur meri coding language bhi C++ hai Please Sir C++ aur Java main dono mein kr kro Please PLease
c++ mei thoda time lagega.
Bhai mn k veham h tmko, 2din d starting k lecture dekh c++, java same h. Python thora different h
@@anjneykumarsingh4461 exactly, main khud C++ coder hoon magar input lena aur array declaration chhod ke baaki kuch alag nhi lagta mujhe
@@shang_chi4651 yup same here
though u teach well , but i wont recommend anyone to study dp from u
aap smjhaye to acha hai.. lekin.. how can we think and get this logic..??
Beta, A,B,C initally cram kri th na aur fr 20-25 baar dots jod jod k he A ya B bnana aaya th. Ab jab aise he solutions dekh k 200-300 questions kr loge to apne aap thinking capabilty develop ho jayegi aur khud se logic soch paoge aap.
@@Pepcoding Thanx sir, btw ye msg aap krte ho ya apki team😅. Anyways thx
@@seemavashishth2231 sir khud hi karte hain, even doosre teachers ke videos mein bhi comments ka reply sir hi karte hain
😂😂Itna depth mein kisi teacher ko aata bhi nhi hoga LCS, poore utube oe kahin nhi hai ye explanation. Even IIT ke profs ke videos mein bhi behind the scenes waali maths nhi samjhayi gayi hai
wow, this cheers me up. I am glad we at pepcoding could be of help to you. Keep learning. Also, recommend us to your juniors and peers, they may also benefit.
Great Explanation, I can bet that no one could explain this, better than you , after getting your explanation i never needed to see code , saved this for future reference, thanks Sumeet sir for such a wonderful video .