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

Правка en1, от faisal_sohail, 2020-08-13 21:36:23

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=[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 throwsTLE.


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+dp(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

Теги #python 3, #help me, #2d-dp, dp with recursion

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский faisal_sohail 2020-08-14 04:11:35 48 Tiny change: '[(i,j)]=1+dp(i-1,j-1)\' -> '[(i,j)]=1+lcs(i-1,j-1)\'
en1 Английский faisal_sohail 2020-08-13 21:36:23 2625 Initial revision (published)