Edit Distance | Recursion | Memo | Bottom Up | DP On Strings | Leetcode 72 | DP Concepts & Qns-21
47Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 22nd Video of our Playlist "DP Concepts & Qns" by codestorywithMIK
This is the fourth video of the "DP On Strings" series in this playlist.
In this video we will try to solve a very good and famous DP problem : Edit Distance (Leetcode - 72)
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Edit Distance | Recursion | Memo | Bottom Up | DP On Strings | Leetcode 72 | DP Concepts & Qns-21 | codestorywithMIK
Company Tags : Amazon, Goldman Sachs, Microsoft, Google
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/Edit%20Distance.cpp
Leetcode Link : https://leetcode.com/problems/edit-distance/
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My Recursion Concepts Playlist : https://www.youtube.com/watch?v=pfb1Zduesi8&list=PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Approach Summary :
Sure, here's a small summary of each approach:
1. **Approach-1 (Recur + Memo, starting from m, n):**
- This approach uses recursion with memoization.
- It starts comparing the strings from the end.
- If the characters at the current positions are equal, it moves to the next positions in both strings.
- If the characters are not equal, it considers three operations: insert, delete, and replace, and recursively calculates the minimum cost for each operation.
- Time Complexity: O(m*n) where m and n are the lengths of the input strings.
- Space Complexity: O(m*n) for memoization table t.
2. **Approach-2 (Recur + Memo, starting from i = 0, j = 0):**
- Similar to Approach-1, but it starts comparing the strings from the beginning.
- It considers the lengths of the remaining portions of the strings and calculates the edit distance accordingly.
- Time Complexity: O(m*n) where m and n are the lengths of the input strings.
- Space Complexity: O(m*n) for memoization table t.
3. **Approach-3 (Bottom-Up DP derived from Approach-1):**
- This approach uses bottom-up dynamic programming.
- It fills up a 2D table iteratively, where t[i][j] represents the minimum edit distance between the substrings s1[0...i-1] and s2[0...j-1].
- It starts with base cases where either string is empty and iterates through the rest of the table, updating values based on the previous values.
- Time Complexity: O(m*n) where m and n are the lengths of the input strings.
- Space Complexity: O(m*n) for the bottom-up dynamic programming table t.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
03:56 - Thought Process
06:00 - Tree Diagram
19:51 - Story To Code
26:21 - Coding Recursion+Memo - 1
31:11 - Understanding Recursion+Memo - 2
41:13 - Coding Recursion+Memo - 2
43:19 - Why I prefer Recursion+Memo - 2
49:14 - Bottom Up
56:11 - Coding Botton Up
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024