faisal_sohail's blog

By faisal_sohail, history, 7 weeks ago, In English

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

 
 
 
 
  • Vote: I like it
  • -15
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it
  1. It's still O(MN) because each state is only computed once (states may get visited multiple times, but it's an O(1) return statement after it's computed the first time). That being said, I'm not a Python expert, but I think your top-down approach might be significantly slower because Python dictionaries are hash tables, so it's a more complex O(1) get compared to array indexing. Also, recursion in Python might be slower in general.

  2. Seems fine, I think you meant to type dp[(i,j)]=1+lcs(i-1,j-1) instead of dp[(i,j)]=1+dp(i-1,j-1).

  3. Top-down might be more intuitive if you think of dp as "smart recursion", since it's literally a recursive function. Ultimately depends on you. Once you get familiar enough, I don't think you need to bother implementing both top-down and bottom-up.

  4. Idk what your thought process was, but I think the implementation was the issue here, not the idea.

  5. Think about what information is important to retain in subproblems, and those make up your dp states.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by faisal_sohail (previous revision, new revision, compare).