NC127 最长公共子串

题目描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串 题目保证str1和str2的最长公共子串存在且唯一。 (子串意味着是连续的)

输入

"1AB2345CD","12345EF"

返回值

"2345"

动态规划法

先确定状态,f(i, j)表示str1中前i个字符和str2中前j个字符中的最长公共子序列的长度

但这样写不出状态转移方程,因为这里 求解公共连续字符串 是没法形成递推关系的,因此增加限制条件:

f(i, j)表示str1中前i个字符和str2中前j个字符中的最长公共子序列的长度,且以第i个字符和第j个字符为结尾

可以简单写出状态转移方程

str1[i] == str2[j] 时,f[i][j] = f[i-1][j-1] + 1

str1[i] != str2[j] 时,f[i][j] = 0

但还有个问题,这个动态规划不能直接得到答案,需要用变量maxLength保存最长的长度

边界条件为:

i = 0 或 j = 0 时, f[i][j] = 0

class Solution:
    def LCS(self , str1 , str2 ):
        
        maxLen = 0
        endIndex = 0
        
        f = [[0 for j in range(len(str2)+1)] for i in range(len(str1)+1)]
        
        for i in range(1, len(str1)+1):
            for j in range(1, len(str2)+1):
                if (str1[i-1] == str2[j-1]):
                    f[i][j] = f[i-1][j-1] + 1
                else:
                    f[i][j] = 0
                if maxLen < f[i][j]:
                    maxLen = f[i][j]
                    endIndex = i # end index of the first string
        
        # print(maxLen)
        return str1[endIndex-maxLen:endIndex]

 

此题可以对比  最长公共子序列 一起看

 

参考:

https://www.nowcoder.com/activity/oj

 

上一篇:你可能不知道的java、python、JavaScript以及jquary循环语句的区别


下一篇:NC127—最长公共子串