Interleaving Strings - Dynamic Programming - Leetcode 97 - Python

0:00 - Read the problem
4:13 - Drawing Explanation
12:35 - Coding Explanation

leetcode 97

#dynamic #programming #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[dollyvishwakarma]

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)

[pengtroll]

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!

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

[joy]

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

[khado]

This makes the most sense to me for optimal solution:
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
if m > n:
s1, s2 = s2, s1
m, n = n, m
dp = [False] * (m + 1)
for j in range(n, -1, -1):
for i in range(m, -1, -1):
res = False
if i == m and j == n:
res = True
if i < m and s1[i] == s3[i + j] and dp[i + 1]:
res = True
if j < n and s2[j] == s3[i + j] and dp[i]:
res = True
dp[i] = res
return dp[0]

[stunseed]

So one thing i realized about dp programming problems so far is that the top down approach usually just comes down a to a decision tree, and when you can come up with a clean decision tree, i.e you're not adding unnecessary parameters to your recursion, you can simple throw a cache at it with ur arguments as the key, and voila it just works.

[tnmyk_]

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

[yassineac]

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

[alokesh]

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

[juliahuanlingtong]

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

[AnandKumar-kzls]

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

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

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

[GetToKnowShaggy]

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

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

How does this solution take into account the fact that |n - m| <= 1 ?

[kareemadesola]

Using the memoization technique, you could just use an hash set since it is always going to 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)]

[dragonthis]

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

[vedantshinde]

That explanation with choice diagram was on point!

[dheepthaaanand]

dp cache is storing if it's not possible to complete the target string from i+j index till end if we use s1 from ith index and s2 from jth index
Hence dp[0, 0] is the final answer
We need to cache False because we can come to the same combination of i, j if we start out differently.
However we don't need to cache True, because we are going to larger indices only if the previous indices match, so if we are able to calculate that say dp[4, 6] is True, it means we could form target string from index 10 till the end with s1[4:] and s2[6:], but we got to this part of the logic only because the previous indices also matched. So that means we can directly return True as it's the final soln