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

import java.util.*;


public class Solution {
   
   //dp[i][j],表示字符串1以i位置元素结尾和字符串2以j位置结尾的最长公共子序列
    public String LCS (String s1, String s2) {

        //1建表
        int m =  s1.length();
        int n = s2.length();
        String [][] dp = new String[m+1][n+1];

       // 2.初始化null为“ ”
        for(int i=0;i<=m;i++){
            for(int j=0;j<=n;j++){
                dp[i][j] = "";
            }
        }

        //3.填表
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+s1.charAt(i-1);
                }else{
                    if( 
                    dp[i-1][j].length()>dp[i][j-1].length()){
                        dp[i][j] = dp[i-1][j];
                    }else{
                        dp[i][j] = dp[i][j-1];
                    }
                }
            }
        }
        if(dp[m][n].length()==0){
            return "-1";
        }
        return dp[m][n];
    }
}