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

动态规划加递归算法

import java.util.*;


public class Solution {
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        // write code here
        int m=s1.length()+1;
        int n=s2.length()+1;
        int [][]dp=new int[m][n];
      //先设置初始值
        for(int i=0;i<m;i++){
            dp[i][0]=0;
        }
        for(int j=0;j<n;j++){
            dp[0][j]=0;
        }
        for(int i=1;i<=s1.length();i++){
            for(int j=1;j<=s2.length();j++){
                if(s1.charAt(i-1)==s2.charAt(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];
                }
            }
        }
        String res=LCSCon(dp,s1,s2,s1.length(),s2.length()).toString();
        return res.equals("")?"-1":res;
    }
    private StringBuilder LCSCon(int [][]dp,String s1,String s2,int i,int j){
        if(i==0){
            return new StringBuilder();
        }
        if(j==0){
            return new StringBuilder();
        }
        if(s1.charAt(i-1)==s2.charAt(j-1)){
            StringBuilder t=LCSCon(dp,s1,s2,i-1,j-1);
            return t.append(s1.charAt(i-1));
        }else if(dp[i-1][j]>=dp[i][j-1]){
            return LCSCon(dp,s1,s2,i-1,j);
        }else {
            return LCSCon(dp,s1,s2,i,j-1);
        }

    }
}