Interleaving Strings - Dynamic Programming - Leetcode 97 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/interlea...
0:00 - Read the problem
4:13 - Drawing Explanation
12:35 - Coding Explanation
leetcode 97
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#dynamic #programming #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@NeetCode]

🚀 neetcode.io/ - A better way to prepare for Coding Interviews 🥷 Discord: discord.gg/ddjKRXPqtk 🐦 Twitter: twitter.com/neetcode1

[@8359s]

7:40 DUDE, I watched 3 other videos and couldn't grasp that part until I watched yours! Thank you.

[@dollyvishwakarma2]

In the top down memoization approach, a condition is missing when the input s1 and s2 are empty but we have some characters in s3: class Solution: def isInterleave(self, s1: str, s2: str, s3: str) -> bool: dp = {} if len(s1) + len(s2) != len(s3): return False def dfs(i, j): if i == len(s1) and j == len(s2): return True if (i, j) in dp: return dp[(i, j)] if i < len(s1) and s1[i] == s3[i+j] and dfs(i+1, j): return True if j < len(s2) and s2[j] == s3[i+j] and dfs(i, j+1): return True dp[(i,j)] = False return False return dfs(0,0)

[@akshatsinghbodh3067]

he wrote the condition for it if len(s1)+len(s2) != len(s3): return False

[@vaibhavsoni2437]

@@akshatsinghbodh3067 in bottom-up, not in top-down. Read carefully!

[@HalfJoked]

This was super helpful. Here's an O(N) solution I made based off this, given we only have to track 2 rows of our grid at once. def isInterleave(self, s1: str, s2: str, s3: str) -> bool: if len(s1) + len(s2) != len(s3): return False dp, prev = [False] * (len(s2)+1), [False] * (len(s2)+1) for i in range(len(s1), -1, -1): for j in range(len(s2), -1, -1): dp[j] = False if i == len(s1) and j == len(s2): dp[j] = True if i < len(s1) and s1[i] == s3[i + j] and prev[j]: dp[j] = True if j < len(s2) and s2[j] == s3[i + j] and dp[j+1]: dp[j] = True dp, prev = prev, dp return prev[0]

[@pengtroll6247]

Bro these are the best algorithms videos I have ever seen. I love the visuals and the step by step process in solving the problems. Keep it up!

[@juliahuanlingtong6757]

OMG!!!Though both iterate the strings from front to back and back to front would work, your technique here makes the base case way more sensable! Like the walk through from recursive all the way up to bottom up dp! ♥️♥️♥️

[@tnmyk_]

I am glad you gave both top-down and bottom-up solutions. Thanks a lot!

[@kywei7485]

Excellent explanation! The problem is really complicated, but your video explains really well!

[@vedantshinde2277]

That explanation with choice diagram was on point!

[@AnandKumar-kz3ls]

the example in the video was the test case that get failed by my code. your channel is gold keep it up

[@MianyunNi]

I am obsessed with your explanation! You become my no.1 idol

[@adityan5302]

Excellent memoization solution. Loved it

[@joy79419]

I am just happy that the greatest leetcode content creator had his first sponsor

[@mohithadiyal6083]

The best explanation I can ever find 😁😁👍🏻

[@alokesh985]

This is how DP should be taught! Amazing stuff. Please keep up the good work. I would happily pay for a full-fledged DP course taught by you

[@algorithmo134]

Hi NeetCode can you do a lecture on algorithm design and analysis? Thank you so much for your hard work!

[@tushartiwari7929]

Ninja level teaching❣

[@kentsang9376]

Best teaching

[@vatsalsharma5791]

Best❤️ Plzz try to make more videos on hard algorithms like dp, recursion, backtracking and graph algo Thankyou so much ❤️

[@begula_chan]

Just thanks, that's the best solution

[@iced_espresso_2717]

How the solution could make sure | m - n |

[@karlocehulic515]

I think no metter how you arrsnge your substrings from s1 and s2 condition will be met. So therefor, in every case condition is already met.

[@consistentthoughts826]

Hi Bro If you do videos on system design it will be amazing

[@user-vs1jd4kp4h]

Did actually try to solve this question with two pointers first, and had a fall realizing its tough to decide which strings to take

[@licokr]

I've tried to write code without seeing your code, but of course, the logic is the same as yours though. I can't say that I fully understand, but I know it will keep better. Without your videos, I may've just moved on to a next question. Thank you!

[@yassineacherkouk]

I spend 45 min trying to figure out the tabulation solution but i can't your a hero men.

[@Sulerhy]

Decision tree! you're the best

[@raylei4700]

Thanks for the awesome explanation. Can you elaborate more on how is this condition "|m - n|

[@mohinishdaswani9836]

No matter how you divided the strings to form the target string, this condition will always be met.

[@kareemadesola6522]

Using the memoization technique, you could just use an hash set since it is always going to return False

[@shrn]

Good !dea

[@dragonthis7948]

hi can i ask how did u take into account that |m-n| < 1 is accounted for in the algorithm?

[@bigrat5101]

Hi NC, can I ask, why we have to cache the False to dp{} not just simply return the False then end the recursion?

[@shuvbhowmickbestin]

yeah same question.

[@venkyvids]

How can this solution be extended for when s3 is an interleaving of loops s1 and s2?

[@manpreetsinghrana7751]

In the memoization soln, dp[i][j] is never set to true.

[@starstarhaha]

yes

[@ashisranjandey7541]

How are we making sure that it is not a concatenation? (a+b) = c? we have to check in base case . right?

[@tanyakemkar310]

thanks

[@meeradad]

I am puzzled by the recurrent dfs solution. After each of the lines 12, 14 return True. But before returning True, should not th dp[(i,j)] be set to True for memoization just as in the return False case, dp[(i.j)] is set to False?

[@laksh9084]

why is he checking i < len(s1) when we are already iterating from s1 to 0 ... what's the point here?

[@jayjw1]

We do this because if we check for the condition dp[i + 1][j] we will be checking an out of bounds array position which will throw an error in python..

[@shuvbhowmickbestin]

what's the need of using a hashmap when all we're storing in it for the keys are false values? Can't we use a set instead and whenever the element is present in the set can we not return false?

[@PedanticAnswerSeeker]

here is the way if you want to do it bottom up if len(s1) + len(s2) != len(s3): return False # Create a 2D array to store the results of subproblems dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)] # Base case: Empty strings interleave to form an empty string dp[0][0] = True # Fill in the first row (s1 is empty) for j in range(1, len(s2) + 1): dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1] # Fill in the first column (s2 is empty) for i in range(1, len(s1) + 1): dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1] for i in range(1, len(s1) + 1): for j in range(1,len(s2) + 1): dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or \ (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]) return dp[len(s1)][len(s2)]

[@ChanChan-pg4wu]

Top notch solution and explanation! I have solved this question before but keep forgetting the correct thinking process. I guess more practice is the way to go. But on top of that, any suggestions to keep the learning in our brain rather than repeated revisiting?

[@himanshut117]

I do struggle with this alot. I guess there is thing, "Actually understanding the problem and fooling yourself that you understood it". If u have understood the logic behind maybe that can hit you in any question you come up with. That is I guess people do CP in codeforces cause you get to experience lot of new problems. While solving these problems think you are collecting tools (logics, thinking process, what thought made u take wrong path for the problem, the patterns etc). This will 100% help you future problems.

[@ersinerdem7285]

Are these 2D true DP solutions really expected to come up in an interview? It just sounds too much at the current state of my mind power :)

[@willw4096]

4:50 6:33 10:20

[@Martelagelo]

FYI your DFS solution does not pass all test cases. I get the point of this video is to highlight the DP solution but you shouldn't show incorrect code. Case that does not pass: s1: "" s2: "" s3: "a"

[@CharlesGreenberg000]

Simple solution: add this before the call to dfs() if len(s1)+len(s2)!=len(s3): return False

[@Ben-pb7ct]

Anyone can modify Java’s solution from bottom-up to top-down? I don’t find the reason why we need to do it reversely?

[@user-gg1jr2hj5o]

How does this solution take into account the fact that |n - m|

[@themagickalmagickman]

Could someone explain why this doesnt work, it appears to do the same exact thing? setting dp[i][j] = dp[i+1][j] should be the same as setting it to True or False as needed, right? dp = [[False for j in range(len(s2)+1)] for i in range(len(s1)+1)] dp[-1][-1] = True for i in range(len(s1),-1,-1): for j in range(len(s2),-1,-1): if i < len(s1) and s1[i] == s3[i+j]: # THIS LINE IS CHANGED dp[i][j] = dp[i+1][j] if j < len(s2) and s2[j] == s3[i+j]: # THIS LINE IS CHANGED dp[i][j] = dp[i][j+1] return dp[0][0]

[@athenalin6360]

Why I= len(s1) and j =len(s2) return true? What if the first character does not match either one?

[@dumbfailurekms]

Then it will return false because i and j start 0..

[@user-mu7kc6yo9q]

wow

[@IK-xk7ex]

Hello, the proposed Backtracking solution has a mistake. It will return wrong result 'true' for a test case s1="a", s2="", s3="c"

[@dumbfailurekms]

if len(s1) + len(s2) != len(s3): return False he said that at the start of the video too

[@sudheerk9347]

Sad to see this as Medium. This is definitely Hard for the most optimized solution (i.e., DP). Though it is a medium for DFS (memoization). I did some search in internet on Memoization and DP. Memoization = O(n^2), DP = O(n) time. It would be great if you can make a video on time complexity difference between Memoization and DP in general.

[@rahulnegi456]

how is DP O(n) ? we have two full for loops there.

[@ss-dy1tw]

I think your code is not working in leetcode, it is failing with case s1="a", s2="" , s3="c", try and let me know

[@tsunghan_yu]

Just add this check: if len(s1) + len(s2) != len(s3): return False

[@Progamer-fq8st]

Another approach, super messy but works unordered_map mp; class Solution { public: bool isscramble(string s1, string s2, string s3, int index1, int index2, int index3, int str){ if(index3 == s3.size()){ return true; } if(index1 == s1.size() && str == 0){ return false; } if(index2 == s2.size() && str == 1){ return false; } string temp = to_string(index1); temp.push_back(' '); temp.append(to_string(index2)); temp.push_back(' '); temp.append(to_string(index3)); temp.push_back(' '); temp.append(to_string(str)); if(mp.find(temp) != mp.end()){ return mp[temp]; } bool ans; if(str == 0){ if(s1[index1] == s3[index3]){ ans = isscramble(s1,s2,s3,index1+1, index2, index3+1, 0) || isscramble(s1,s2,s3,index1+1, index2, index3+1, 1); } else{ return mp[temp] = false; } } else{ if(s2[index2] == s3[index3]){ ans = isscramble(s1,s2,s3,index1, index2+1, index3+1, 0) || isscramble(s1,s2,s3,index1, index2+1, index3+1, 1); } else{ return mp[temp] = false; } } return mp[temp] = ans; } bool isInterleave(string s1, string s2, string s3) { mp.clear(); if(s3.size() != (s1.size() + s2.size())){ return false; } bool ans = isscramble(s1,s2,s3,0,0,0,0) || isscramble(s1,s2,s3,0,0,0,1); return ans; } };

[@glenfernandes5248]

The recursive soln. fails leetcode testcases.

[@KeshavKumar69420]

Just add a check for sum of length of str1 and str2. If the sum is not equal to length of str3 then return False. That check was present in bottom up soln.

[@alokesh985]

The regular recursive soln will time out. However, the memoization actually was faster than DP for me in leetcode