题解 | #最长公共子串#

package main

/**
 * longest common substring
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @return string字符串
*/
func LCS( str1 string ,  str2 string ) string {
  	// 和公共子序列差不多的思想，区别在于当两个字不相同时，这里需要把公共字串置空
    // dp[n][m]=dp[n-1][m-1]+str1[n]
    // dp[n][m]=""
    if len(str1)==0||len(str2)==0{return ""}
    result:=""
    dp:=make([][]string,len(str1)+1)
    for i:=0;i<len(dp);i++{
        dp[i]=make([]string,len(str2)+1)
    }
    for i:=1;i<=len(str1);i++{
        for j:=1;j<=len(str2);j++{
            if str1[i-1]==str2[j-1]{
                dp[i][j]=dp[i-1][j-1]+string(str1[i-1])
                if len(dp[i][j])>len(result){
                    result=dp[i][j]
                }
            }else{
                dp[i][j]=""
            }
        }
    }
    return result
}