 # Largest Common Sub-strings| NEED HELP | DP | TOP DOWN

hello there, I tried to solve a problem 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=*(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==B` , `dp=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+lcs(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 is 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