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

package main

func LCS(s1 string, s2 string) string{
    m,n := len(s1), len(s2)

    var dp = make([][]int, m+1)
    for i:=0; i<m+1; i++{
        dp[i] = make([]int, n+1)
    }

    for i:=1; i<m+1; i++{
        for j:=1; j<n+1; j++{
            if s1[i-1] == s2[j-1]{
                dp[i][j] = dp[i-1][j-1] + 1
            } else{
                dp[i][j] = max(dp[i][j-1] , dp[i-1][j])
            }
        }
    }

    var res string

    for i,j:=m,n; dp[i][j] > 0;{
        if s1[i-1] == s2[j-1]{
            res = string(s1[i-1]) + res
            i--
            j--
        } else if dp[i][j-1] > dp[i-1][j]{
            j--
        } else{
            i--
        }
    }

    if res == ""{
        return "-1"
    }

    return res
}

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

    return b
}

// package main

// func LCS(s1 string, s2 string) string{
//     m, n := len(s1), len(s2)
//     var dp = make([][]int, m+1)
//     for i:=0; i<m+1; i++{
//         dp[i] = make([]int, n+1)
//     }

//     for i:=1; i<m+1; i++{
//         for j:=1; j<n+1; j++{
//             if s1[i-1] == s2[j-1]{
//                 dp[i][j] = dp[i-1][j-1]+1
//             }else{
//                 dp[i][j] = max(dp[i][j-1], dp[i-1][j])
//             }
//         }
//     }

//     var res string

//     for i, j := m, n; dp[i][j] > 0;{
//         if s1[i-1] == s2[j-1]{
//             res = string(s1[i-1]) + res
//             i--
//             j--
//         } else if dp[i][j-1] > dp[i-1][j]{
//             j--
//         } else{
//             i--
//         }
//     }

//     if res == "" {
//         return "-1"
//     }

//     return res
// }

// func max(a, b int) int{
//     if a > b{
//         return a
//     }
//     return b
// }