Longest Common Subsequence (LeetCode 1143) | Full Solution with a natural explanation

  Рет қаралды 16,719

Nikhil Lohia

Nikhil Lohia

Күн бұрын

Пікірлер: 46
@jaytran247
@jaytran247 11 күн бұрын
I came across some other popular videos explaining this problem, and this is so far the most favorite video which contain the explanation that I am looking for. Thanks alot
@anushakatika9229
@anushakatika9229 11 ай бұрын
Great explanation. I have seen many dp solution but nobody explanation as clearly as you did
@nikoo28
@nikoo28 10 ай бұрын
Happy you feel this
@KoundinyaKoorapati-o8v
@KoundinyaKoorapati-o8v Ай бұрын
The best explanation I have come across for this problem till date 👍
@matthewzarate8851
@matthewzarate8851 20 күн бұрын
Amazing explanation of the problem statement and the solution! We had this question in lecture last week and I found it really confusing, thanks for helping out with this Nikhil!!
@atifakhtar8828
@atifakhtar8828 Ай бұрын
BEST EXPLANATION TILL DATE ...WOW AMAZING SIR .....Respect +++++++++++++++
@Hayat26474
@Hayat26474 8 ай бұрын
your way of teaching is just great sir , Thanku !!
@nikoo28
@nikoo28 8 ай бұрын
Thanks and welcome
@ashok2089
@ashok2089 3 ай бұрын
Thanks for clearly explaining DP Bottom up approach in normal array traversal instead of reverse traversal. Thanks!
@Usseeer_kaizen
@Usseeer_kaizen 7 ай бұрын
great approach, thanks teacher, the best explanation I have ever seen
@ishaqniloy1532
@ishaqniloy1532 9 ай бұрын
Best explanation ever!
@rode_atharva
@rode_atharva 7 ай бұрын
while(true){ print("great explenation") }
@nikoo28
@nikoo28 6 ай бұрын
😊
@atifakhtar8828
@atifakhtar8828 Ай бұрын
this is everything ...all dp is here
@urvashichaurasia6284
@urvashichaurasia6284 3 ай бұрын
Great explanation sir . Please start a playlist of hard DSA problems.
@NinjaCoders
@NinjaCoders Ай бұрын
You are great Bro, just keep doing
@vivekkumaryadav9862
@vivekkumaryadav9862 Жыл бұрын
Thanks a lot sir ..u make hard ques in easy way
@sheikhmkrifat7749
@sheikhmkrifat7749 3 ай бұрын
class Solution { public int longestCommonSubsequence(String text1, String text2) { // Ensure text1 is the longer string to minimize space usage if (text2.length() > text1.length()) { return longestCommonSubsequence(text2, text1); } // Convert strings to character arrays for easy access char[] s1 = text1.toCharArray(); char[] s2 = text2.toCharArray(); // Create two arrays to store the lengths of longest common subsequences int[] previousRow = new int[s2.length + 1]; int[] currentRow = new int[s2.length + 1]; // Loop through each character in s1 for (int i = 0; i < s1.length; i++) { // Loop through each character in s2 for (int j = 0; j < s2.length; j++) { // If characters match, increment the length from the previous row and previous column if (s1[i] == s2[j]) { currentRow[j + 1] = previousRow[j] + 1; } else { // If characters don't match, take the maximum length by ignoring one character either from s1 or s2 currentRow[j + 1] = Math.max(currentRow[j], previousRow[j + 1]); } } // Swap rows: currentRow becomes previousRow for the next iteration int[] temp = previousRow; previousRow = currentRow; currentRow = temp; } // The length of the longest common subsequence is in the last element of previousRow return previousRow[s2.length]; } public static void main(String[] args) { Solution solution = new Solution(); // Test cases System.out.println(solution.longestCommonSubsequence("abcde", "ace")); // Output: 3 System.out.println(solution.longestCommonSubsequence("abc", "abc")); // Output: 3 System.out.println(solution.longestCommonSubsequence("abc", "def")); // Output: 0 } } this is true dynamic solution
@acthanger7420
@acthanger7420 9 ай бұрын
you are such a nice teacher)
@hoddybhaba6704
@hoddybhaba6704 Жыл бұрын
Nice explanation bro👏
@lo_sten
@lo_sten 3 ай бұрын
Could you also do a topdown approach please
@inakizeusreinante7729
@inakizeusreinante7729 Күн бұрын
Sir i love you so much
@atifakhtar8828
@atifakhtar8828 Ай бұрын
sir sir sir you are a legend
@vishwasankar14
@vishwasankar14 8 ай бұрын
Thank you so much brother!
@himanshuajwani9226
@himanshuajwani9226 5 ай бұрын
amazing and detail explained
@jayaveeran1
@jayaveeran1 5 ай бұрын
This is no less than excellent !
@EgorChebotarev
@EgorChebotarev 6 ай бұрын
nice explanation
@rupeshpatil6957
@rupeshpatil6957 Ай бұрын
Thanks Brother
@subee128
@subee128 10 ай бұрын
Thanks
@AmalGeorge-xt3kq
@AmalGeorge-xt3kq Жыл бұрын
Sir, in this problem you are iterating from i=1, j=1. but, in the given example the memoization table has dp[0][1]=1. how does it got 1 in program
@nikoo28
@nikoo28 Жыл бұрын
when you initialize a 2D array, all elements are initialized to 0 by default. That is why I run my loop from i=1, j=1
@anushakatika9229
@anushakatika9229 11 ай бұрын
Thanks!
@nikoo28
@nikoo28 11 ай бұрын
Thank you so much for the support.
@shadowwolf5578
@shadowwolf5578 Жыл бұрын
sir can you explain the backtracking part? To print longest common subsequence
@nikoo28
@nikoo28 Жыл бұрын
i will make a video on it soon
@alisheheryar1770
@alisheheryar1770 5 ай бұрын
No recursive brute force for this??????????????
@exe.m1dn1ght
@exe.m1dn1ght Жыл бұрын
Hello Sir, can you make a good video about iteration and loops ? And I hope you will not give the example " You need to repeat 10 times hello, how would you do it ? " ..
@nikoo28
@nikoo28 Жыл бұрын
What do you want to understand when it comes to loops. I can think on those lines.
@exe.m1dn1ght
@exe.m1dn1ght Жыл бұрын
@@nikoo28 I dont even know what i'm trying to understand .. I solved 380 problems on LeetCode and still can't really understand them a hundred percent, I use for and while loops to solve problems by pure instinct .. It's like these loops are simulating real world but at a text level , for example if i want to drink a glass of water the translation to text is while ( i still have water in the glass) i keep doing the drinking logic and decrease the water in the glass, but then you have conditions like while (i still have the light on) i keep reading , but that condition is changing based on something decreasing or increasing because mathematics is present in everything right ? we can quantify everything if we really think about it no ? I'm trrying to create this clear picture in my mind comparing programming text and real life and real life to programming text .. Am i overthinking this or I am going crazy ? Please help Sir !
@RamuKumar-yl4yp
@RamuKumar-yl4yp Жыл бұрын
@ankurbassi2667
@ankurbassi2667 Жыл бұрын
@@exe.m1dn1ght I never imagined a way of comparison like this. I think you should start making videos of how are you relating with real life. A different perspective which will be very cool to know
@exe.m1dn1ght
@exe.m1dn1ght Жыл бұрын
@@ankurbassi2667 i had a very wrong perspective about this, i figured out its just instructions, like the ones you read on a cooking recipe. I am so happy i fixed my problem, it was all about how i see it. Anyway this dude didnt even helped me at all
@ifrahshahid8802
@ifrahshahid8802 3 ай бұрын
best
@luiggymacias5735
@luiggymacias5735 9 ай бұрын
sosote rocafuerte
@nikoo28
@nikoo28 9 ай бұрын
gracias!!
@dmytro.pyvovarenko
@dmytro.pyvovarenko 9 ай бұрын
cudo!
Longest common subsequence | Leetcode #1143
18:45
Techdose
Рет қаралды 61 М.
2 MAGIC SECRETS @denismagicshow @roman_magic
00:32
MasomkaMagic
Рет қаралды 34 МЛН
Human vs Jet Engine
00:19
MrBeast
Рет қаралды 200 МЛН
Longest Common Subsequence- Dynamic Programming | Data structures and algorithms
25:47
Longest Common Subsequence | Recursion | Memo | Optimal | Leetcode 1143
39:18
LeetCode was HARD until I Learned these 15 Patterns
13:00
Ashish Pratap Singh
Рет қаралды 546 М.