题解 | #最长公共子序列(二)#

package main

/**
 * longest common subsequence
 * @param s1 string字符串 the string
 * @param s2 string字符串 the string
 * @return string字符串
*/
func LCS( s1 string ,  s2 string ) string {
    // dp[n][m]=max(dp[n-1][m],dp[n][m-1])|dp[n-1]dp[m-1]+1
    dp:=make([][]string,len(s1)+1)
    for i:=range dp{
        dp[i]=make([]string,len(s2)+1)
    }

    for i:=1;i<len(s1)+1;i++{
        for j:=1;j<len(s2)+1;j++{
            if s1[i-1]==s2[j-1]{
                dp[i][j]=dp[i-1][j-1]+string(s1[i-1])
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
            }
        }
    }
    if dp[len(s1)][len(s2)]==""{return "-1"}
    return dp[len(s1)][len(s2)]
}

func max(a,b string)string{
    if len(a)>len(b){
        return a
    }
    return b
}