Interleaving Strings - Dynamic Programming - Leetcode 97 - Python

[@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!

[@arunsp767]

My question is, where is a situation where we save True into dp? I don't see dp[(I,j)] = True anywhere

[@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]

[@kvtys]

thought you meant time complexity - was gonna say you should win a nobel prize lol

[@arunsp767]

Ran your code and it took 25 passes to this test case abcd, efgh, abcsefgh

[@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!

[@tnmyk_]

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

[@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

[@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! ♥️♥️♥️

[@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.

[@joy79419]

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

[@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?

[@AnandKumar-kz3ls]

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

[@sanjai_rs7]

Bro you are everywhere

[@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!

[@kareemadesola6522]

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

[@shrn]

Good !dea

[@MrShag23]

this might be the best dp explanation I've seen so far ngl

[@BirajDahal-z6u]

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

[@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..

[@MianyunNi]

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

[@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)]

[@yassineacherkouk]

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

[@pravinchoudhari353]

The only diversion in this questions was to make sure that we use s1 and s2 alternatively to that |m-n|

[@manpreetsinghrana7751]

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

[@starstarhaha]

yes

[@kywei7485]

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

[@vedantshinde2277]

That explanation with choice diagram was on point!

[@ashisranjandey7541]

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

[@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?

[@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.

[@consistentthoughts826]

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

[@adityan5302]

Excellent memoization solution. Loved it

[@НикитаБаринов-р6г]

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

[@dragonthis7948]

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

[@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.

[@mohithadiyal6083]

The best explanation I can ever find 😁😁👍🏻

[@willw4096]

4:50 6:33 10:20

[@begula_chan]

Just thanks, that's the best solution

[@Sulerhy]

Decision tree! you're the best

[@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?

[@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.

[@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

[@vatsalsharma5791]

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

[@algorithmo134]

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

[@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

[@raylin2527]

Love this video!!!

[@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 :)

[@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..

[@tushartiwari7929]

Ninja level teaching❣

[@wanderer4954]

I watched this solution in 0.75 speed. still had to rewatch it.

[@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]

[@kunindsahu974]

I'd recommend putting your question to Claude, I had the same question and it gave me a whole lot of clarity.

[@kunindsahu974]

A small snippet from Claude - "The issue with the incorrect version is that it doesn't consider both possibilities simultaneously. Here's why: In the correct version, you're checking if the current character matches s1 AND if it's possible to form the string up to the previous character using s1. The same logic applies for s2. In the incorrect version, you're only checking if the current character matches, and then directly assigning the previous state. This doesn't account for cases where both s1 and s2 could potentially contribute to the current position. The correct version uses True assignment, which allows for the possibility that either s1 or s2 could work. The incorrect version always assigns the previous state, which might inadvertently overwrite a valid solution."

[@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?

[@kentsang9376]

Best teaching

[@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; } };

[@tanyakemkar310]

thanks

[@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

[@서울_9반_김노아]

wow

[@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