题解 | #最长公共子串#

package main


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * longest common substring
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @return string字符串
 */
//方法1:暴力法；每个字符串的位置进行匹配；计算出最长的情况；O(m*n!);m是较长的；n是较短的字符串；两个字符串中的任意两个位置进行匹配
//暴力法存在重复计算的问题；
//优化方法2:利用动态规划；计算出已经计算过的那些路径的最长位置；动态规划；自下而上的计算方法；二维动态规划
func LCS(str1 string, str2 string) string {
	// write code here
	if len(str1) == 0 || len(str2) == 0 {
		return ""
	}
	//初始化动态规划值
	dp := make([][]int, len(str1))
	for i, c1 := range str1 {
		tmp := make([]int, len(str2))
		for j, c2 := range str2 {
			if c1 == c2 {
				tmp[j] = 1
			} else {
				tmp[j] = 0
			}
		}
		dp[i] = tmp
	}

	//动态规划自下而上的计算
	for i := 1; i < len(str1); i++ {
		for j := 1; j < len(str2); j++ {
			if str1[i] == str2[j] {
				dp[i][j] = dp[i-1][j-1] + 1
			}
		}
	}
	//找到最长的子串长度
	var (
		r, ml int
	)
	for i := 0; i < len(str1); i++ {
		for j := 0; j < len(str2); j++ {
			if dp[i][j] > ml {
				ml = dp[i][j]
				r = i
			}
		}
	}
	return str1[r-ml+1 : r+1]
}