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.
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
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
LCS Returns
You are viewing a single comment's thread. Return to all comments →
The following codes work by pypy 3