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

using System;
using System.Collections.Generic;


class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public string LCS (string s1, string s2) {
        var dp = new int[s1.Length+1,s2.Length+1];
        for(int i = 0; i <= s1.Length; i++){
            dp[i,0] = 0;
        }
        for(int i = 0; i <= s2.Length; i++){
            dp[0,i] = 0;
        }
        for(int i = 1; i <= s1.Length; i++){
            for(int j = 1; j <= s2.Length; j++){
                if(s1[i-1] == s2[j-1]){
                    dp[i,j] = dp[i - 1,j -1] + 1;
                }
                else if(dp[i - 1,j] >= dp[i,j-1]){
                    dp[i,j] = dp[i - 1,j];
                }
                else{
                    dp[i,j] = dp[i,j - 1];
                }
            }
        }

        var res = new List<char>();
        for(int i = s1.Length, j = s2.Length; dp[i,j] > 0;){
            if(s1[i-1] == s2[j - 1]){
                res.Add(s1[i - 1]);
                i--;
                j--;
            }
            else if(dp[i,j] <= dp[i - 1,j]){
                i--;
            }
            else{
                j--;
            }
        }
        res.Reverse();
        return res.Count > 0 ? new string(res.ToArray()) : "-1";
    }
}