题解 | #最长公共子串#

最长公共子串

http://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac

假设dp[i][j]为在str1的i索引位开始和str2的j索引位开始的最长公共子串。

所以当str1[i] == str2[j] and i < len(str1)-1 and j < len(str2) -1时,

dp[i][j] = dp[i+1][j+1] + 1

当str1[i] == str2[j] and i == len(str1)-1 and j == len(str2)-1时,

dp[i][j] = 1

else: dp[i][j] = 0

这样我们倒序循环两个数组就可以获得完整的dp,其中获取dp的最大值及其所在的下标就能得到想要的字符串。完整代码如下:

class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        n1 = len(str1)
        n2 = len(str2)
        begin = 0
        max = 0
        dp = [[0]*n2 for i in range(n1)]
        for i in range(n1-1,-1,-1):
              for j in range(n2-1,-1,-1):
                    if(str2[j] == str1[i] and i < n1-1 and j < n2-1):
                        dp[i][j] = dp[i+1][j+1] + 1
                    elif(str2[j] == str1[i] and (i == n1-1 or j == n2-1)):
                        dp[i][j] = 1
                    else:
                        dp[i][j] = 0
                    if(max < dp[i][j]):
                        max = dp[i][j]
                        begin = i
        return str1[begin:begin+max]
全部评论

相关推荐

nus2201602...:兄弟,你这个简历撕了丢了吧,就是一坨,去找几个项目,理解项目流程,看几遍就是你的了,看看八股就去干了,多看看牛客里别人发出来的简历,对着写,你这写的啥啊,纯一坨
点赞 评论 收藏
分享
ZywOo_求职版:谁问你了....
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 17:58
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务