We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
LCS Returns
LCS Returns
+ 0 comments Here is my solution in java, javascript, python, C ,C++, Csharp HackerRank LCS Returns Problem Solution
+ 0 comments The following codes work by pypy 3
na=len(a) nb=len(b) dp=[[0]*(nb+1) for _ in range(na+1)] for i in range(na): for j in range(nb): if a[i]==b[j]: dp[i+1][j+1]=dp[i][j]+1 else: dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]) suff=[[0]*(nb+1) for _ in range(na+1)] for i in range(na-1,-1,-1): for j in range(nb-1,-1,-1): if a[i]==b[j]: suff[i][j]=suff[i+1][j+1]+1 else: suff[i][j]=max(suff[i+1][j],suff[i][j+1]) cur = dp[na][nb] ret = 0 for i in range(na+1): used=[False]*(256) for j in range(nb): if used[ord(b[j])]==True: continue now=dp[i][j]+ suff[i][j+1] + 1 if now == cur+1: used[ord(b[j])]=True ret+=1 return ret
+ 0 comments Here is LCS Returns problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-LCS-return-problem-solution.html
+ 0 comments Can anyone help me in this?
M=62 def func(c): if(c>='a' and c<='z'): return ord(c)-97 if(c>='A' and c<='Z'): return ord(c)-65 return ord(c)-48 def tutzkiAndLcs(a, b): n=len(a) m=len(b) dp=[] dpr=[] position=[[] for i in range(M)] for i in range(1,m+1,1): position[func(b[i-1])].append(i) for i in range(n+2): dp+=[[0]*(m+2)] dpr+=[[0]*(m+2)] for i in range(1,n+1): for j in range(1,m+1): if a[i-1]==b[j-1]: dp[i][j]=dp[i-1][j-1]+1 else: dp[i][j]=max(dp[i-1][j],dp[i][j-1]) for i in range(n,0,-1): for j in range(m,0,-1): if(a[i-1]==b[j-1]): dpr[i][j]=1+dpr[i+1][j+1] else: dpr[i][j]=max(dpr[i+1][j],dpr[i][j+1]) #print(position) #print(dp) #print(dpr) ans = 0 for i in range(0,n+1,1): for c in range(0,26,1): for j in range(0,len(position[c]),1): p=position[c][j] if(dp[i][p-1] + dpr[i+1][p+1] == dp[n][m]): ans+=1 break print(ans) return ans
+ 0 comments https://codeforces.com/blog/entry/103769#comment-921563
explanation and code
Load more conversations
Sort 23 Discussions, By:
Please Login in order to post a comment