hello there,↵
I tried to solve a [problem](https://leetcode.com/problems/maximum-length-of-repeated-subarray/) which is directly based on the Longest common substring. I solved it quite easily with the `bottom-up` (DP) approach because it seemed more intuitive to me then `top-down` since I just needed to extend to the idea of Lcs(longest common subsequence).↵
↵
below, how is implemented bottom-up approach:↵
↵
~~~~~↵
↵
def findLength(A,B):↵
↵
m,n=len(A),len(B)↵
dp=[0]*(n+1)↵
ans=0↵
for i in range(m):↵
for j in range(n,0,-1):↵
if A[i]==B[j-1]:↵
dp[j]=dp[j-1]+1↵
ans=max(ans,dp[j])↵
else:↵
dp[j]=0↵
return ans↵
~~~~~↵
↵
↵
~~~~~↵
I tried to implement the same using top-down approach but did not succeed. ↵
I would like to share my thought that how I landed on my recursive relation. let `A, B` are two strings are given and `def lcs(i,j):` # function.↵
`dp[i][j]` represents LC_Substring after considering ith elements and jth elements of two string respectively.↵
Now if `A[i]==B[j]` then `dp[i][j] = 1+lcs(i-1,j-1)`↵
else: dp[i][j]=0, also we need check at lcs(i-1,j) and lcs(i,j-1) irrespective of if-else,↵
to clarify my points i would take an example `,A= 'aab' and B='aabb'`,recursive call start with `i=3 and j=4,`↵
since `A[3]==B[4]`,`dp[3][4]=1+lcs(2,3)` but the required output is achieved when we consider `lcs(3,3)` .↵
~~~~~↵
↵
↵
below is the code I submitted which passed `31/54 test cases` and throws` TLE`.↵
↵
~~~~~↵
↵
m,n=len(A),len(B)↵
dp={}↵
ans=0↵
↵
def lcs(i,j):↵
↵
if i==0 or j==0:↵
return 0↵
elif dp.get((i,j)):↵
return dp[(i,j)]↵
if A[i-1]==B[j-1]:↵
dp[(i,j)]=1+dplcs(i-1,j-1)↵
ans=max(ans,dp[(i,j)])↵
else:↵
↵
dp[(i,j)]=0↵
lcs(i-1,j)↵
lcs(i,j-1)↵
return dp[(i,j)]↵
lcs(m,n)↵
return ans↵
~~~~~↵
↵
my queries :↵
↵
~~~~~↵
1. is the time complexity of my top-down approach is O(m*n)?↵
2. is my recursive relation for top-down right?↵
3. it considered good practice for a beginner to solve first top-down then move to bottom-up , but in this case, is it not case that bottom-up seems more intuitive?↵
4. where my thought went process wrong?↵
5. what would be right or efficient way to interpret these types of questions and approach them?↵
~~~~~↵
↵
↵
↵
Thanks a million in advance.↵
happy coding↵
I tried to solve a [problem](https://leetcode.com/problems/maximum-length-of-repeated-subarray/) which is directly based on the Longest common substring. I solved it quite easily with the `bottom-up` (DP) approach because it seemed more intuitive to me then `top-down` since I just needed to extend to the idea of Lcs(longest common subsequence).↵
↵
below, how is implemented bottom-up approach:↵
↵
~~~~~↵
↵
def findLength(A,B):↵
↵
m,n=len(A),len(B)↵
dp=[0]*(n+1)↵
ans=0↵
for i in range(m):↵
for j in range(n,0,-1):↵
if A[i]==B[j-1]:↵
dp[j]=dp[j-1]+1↵
ans=max(ans,dp[j])↵
else:↵
dp[j]=0↵
return ans↵
~~~~~↵
↵
↵
~~~~~↵
I tried to implement the same using top-down approach but did not succeed. ↵
I would like to share my thought that how I landed on my recursive relation. let `A, B` are two strings are given and `def lcs(i,j):` # function.↵
`dp[i][j]` represents LC_Substring after considering ith elements and jth elements of two string respectively.↵
Now if `A[i]==B[j]` then `dp[i][j] = 1+lcs(i-1,j-1)`↵
else: dp[i][j]=0, also we need check at lcs(i-1,j) and lcs(i,j-1) irrespective of if-else,↵
to clarify my points i would take an example `,A= 'aab' and B='aabb'`,recursive call start with `i=3 and j=4,`↵
since `A[3]==B[4]`,`dp[3][4]=1+lcs(2,3)` but the required output is achieved when we consider `lcs(3,3)` .↵
~~~~~↵
↵
↵
below is the code I submitted which passed `31/54 test cases` and throws` TLE`.↵
↵
~~~~~↵
↵
m,n=len(A),len(B)↵
dp={}↵
ans=0↵
↵
def lcs(i,j):↵
↵
if i==0 or j==0:↵
return 0↵
elif dp.get((i,j)):↵
return dp[(i,j)]↵
if A[i-1]==B[j-1]:↵
dp[(i,j)]=1+
ans=max(ans,dp[(i,j)])↵
else:↵
↵
dp[(i,j)]=0↵
lcs(i-1,j)↵
lcs(i,j-1)↵
return dp[(i,j)]↵
lcs(m,n)↵
return ans↵
~~~~~↵
↵
my queries :↵
↵
~~~~~↵
1. is the time complexity of my top-down approach is O(m*n)?↵
2. is my recursive relation for top-down right?↵
3. it considered good practice for a beginner to solve first top-down then move to bottom-up , but in this case, is it not case that bottom-up seems more intuitive?↵
4. where my thought went process wrong?↵
5. what would be right or efficient way to interpret these types of questions and approach them?↵
~~~~~↵
↵
↵
↵
Thanks a million in advance.↵
happy coding↵