最长公共子串lcs动态规划实现

最长公共子串lcs动态规划实现

最长公共子串要求在原字符串中是连续的，而子序列只需要保持相对顺序一致，并不要求连续。

下面我分享一下dp的方法，时间复杂度O(mn)，空间复杂度O(mn)

class Solution: def lcs(self,s1,s2): max_len=0 max_index=0 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 if(dp[i][j]>max_len): max_len=dp[i][j] max_index=i-max_len return max_len,max_index,s1[max_index:max_index+max_len] if __name__=="__main__": solution=Solution() s1='acbac' s2='acaccbabb' max_len,max_index,seq=solution.lcs(s1,s2) print(max_len,max_index,seq)

有兴趣的人可以帮我找找bug哈，我感觉没啥问题，如果能帮我找到bug，那就万分感谢了，哈哈哈

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