解题方法:
首先生成动态规划表dp,生成规则如下:
对于两个字符串str1和str2,dp[i][j]表示将str1[i]和str[j]作为公共子串最后一个字符的长度
非第一行,第一列:
如果str1[i]==str2[j],则dp[i][j] = dp[i-1][j-1]+1
如果str1[i] != str2[j], 则dp[i][j] = 0
第一行或者第一列
第一行:如果str1[i]==str2[0],则dp[i][0] = 1
第一列:如果str1[0] != str2[j], 则dp[0][j] = 1
按照上述规则生成动态规划表dp,时间复杂度为O(MXN),空间复杂度为O(MXN)。查询dp中的最大值,然后向左上方向查找,直到dp值为1,即可得到最终公共子串。
从动态规划表可以看到其大致形式如下图:
因此可以按照图中箭头方向查询两个字符串,并用一个变量记录公共子串的长度,代码如下:
func getMaxLengthCommonString(str1, str2 []rune)[]rune{ chs1 := len(str1) chs2 := len(str2) maxLength := 0 //记录最大长度 end := 0//记录最大长度的结尾位置 rows := 0 cols := chs2-1 for rows < chs1 { i,j := rows, cols length := 0 //记录长度 for i< chs1 && j < chs2 { if str1[i] != str2[j]{ length = 0 }else{ length ++ } if length > maxLength { end = i maxLength = length } i ++ j ++ } if cols > 0 { cols -- }else{ rows++ } } return str1[(end-maxLength+1):(end+1)]}