faisal_sohail's blog

By faisal_sohail, history, 4 years 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

Full text and comments »

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

By faisal_sohail, history, 4 years ago, In English

hello there, i am facing problem in solving dp using top down approach.

`problem 1`

i tried to solve this problem using DP Top down approach (recursively with memoization). got Accepted when submitted this_solution while it gave TLE for other_solution i tried to figure out the reason behind but failed . curious to know, why my second solution gave TLE. ``

` problem 2:`

i tried to solve this_problem of Atcoder using top_down approach,but it shows TLE for two sub-tasks> my_solution_link am i missing any edge case or it just because of recursion or Python?

any help is highly appreciated. along with that i will be glad if u would do code review and suggest ways to make my coding more effective and readable

Thanks a ton in advance. Happy coding

Full text and comments »

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

By faisal_sohail, history, 4 years ago, In English

** hello coders,** ** will you plz give me some intuition about the problem below:** ** i tried to solve it by solve it by dp with memoization recursively but showed max. depth reached error.**

Spiderman is stuck in a difficult situation. His arch enemy the Green Goblin has planted several of his infamous Pumpkin Bombs in various locations in a building. Help Spiderman activate his Spidey Sense and identify the impact zones. He has a blue print of the building which is a M x N matrix that is filled with the characters ‘O’, ‘B’, and ‘W’ where: ‘O’ represents an open space. ‘B’ represents a bomb. ‘W’ represents a wall. You have to replace all of the O’s (open spaces) in the matrix with their shortest distance from a bomb without being able to go through any walls. Also, replace the bombs with 0 and walls with -1 in the resultant matrix. If no path exists between a bomb and an open space replace the corresponding 'O' with -1.

Input: First line of input contains number of test cases T. For each testcase, first line contains space separated M and N respectively. Then M lines will follow containing N characters each.

Output: Print the resultant integer matrix that denotes shortest distance of each open space cell from a bomb in the blue print of the building.

Constraints: 0 <= T <= 50 1 <= M,N <= 10

Example: Sample Input: 1, 3 3, O O O, W B B, W O O,

Sample Output: 2 1 1, -1 0 0 , -1 1 1 ,

Explanation: The walls at (1,0) and (2,0) are replaced by -1. The bombs at (1,1) and (1,2) are replaced by 0. The impact zone for the bomb at (1,1) includes open spaces at index (0,0), (0,1) and (2,1) with distance from bomb calculated as 2,1,1 respectively. The impact zone for the bomb at (1,2) includes open spaces at index (0,3) and (2,2) with distance from bomb calculated as 1,1 respectively.

happy coding.

Full text and comments »

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