牛课网 python 最长公共子序列和最长公共子串的问题（不太懂）

牛课网 python 最长公共子序列和最长公共子串的问题（不太懂）

最近在牛课网上实现了一下最长公共子序列的dp版本，发现ac不了，我怀疑它们把最长公共字串和最长公共子序列搞混了

最长公共子序列的实现为：

## longest common subsequence# @param s1 string字符串 the string# @param s2 string字符串 the string# @return string字符串#class Solution: def LCS(self , s1 , s2 ): # write code here m=len(s1) n=len(s2) dp=[[0]*(n+1) for i in range(m+1)] for i in range(m+1): for j in range(n+1): if(i==0 or j==0): continue elif(s1[i-1]==s2[j-1]): dp[i][j]=dp[i-1][j-1]+1 else: dp[i][j]=max(dp[i][j-1],dp[i-1][j]) i=m j=n lcs='' while(i>0 and j>0): if(s1[i-1]==s2[j-1]): lcs+=s1[i-1] i-=1 j-=1 elif(dp[i][j-1]>=dp[i-1][j]): j-=1 elif(dp[i][j-1]

发现没有ac

当换成最长公共子串的代码的时候：

## longest common subsequence# @param s1 string字符串 the string# @param s2 string字符串 the string# @return string字符串#class Solution: def LCS(self , s1 , s2 ): # write code here max_len=0 res='' if(len(s1)>len(s2)): s1,s2=s2,s1 for i in range(len(s1)): if(s1[i-max_len:i+1] in s2): res=s1[i-max_len:i+1] max_len+=1 if(res==''): return -1 else: return res

结果ac了，而且这还是一个相对暴力的解法，真是不太懂为啥

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。