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

package main

/**
 * longest common subsequence
 * @param s1 string字符串 the string
 * @param s2 string字符串 the string
 * @return string字符串
*/
func LCS( s1 string ,  s2 string ) string {
    len1,len2:=len(s1),len(s2)
    dp:=make([][]string,len1+1)
    for i,_:=range dp{
        dp[i]=make([]string,len2+1)
    }
    for i:=1;i<=len1;i++{
        for j:=1;j<=len2;j++{
            if s1[i-1]==s2[j-1]{
                dp[i][j]=dp[i-1][j-1]+string(s1[i-1])
            }else{
                if len(dp[i-1][j])>len(dp[i][j-1]){
                    dp[i][j]+=dp[i-1][j]
                }else{
                    dp[i][j]+=dp[i][j-1]
                }
            }
        }
    }
    ans:=dp[len1][len2]
    if ans==""{
        return "-1"
    }
    return ans
}