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

import java.util.*;

/**
        根据动态规划的结果进行回溯!
        迭代时,记忆值更新的原因,即迭代方向!
**/
public class Solution {
    
    
    
    public String LCS (String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m+1][n+1]; // dp[i][j] 表示s1以第i-1 个元素为结尾,s2 以j-1 个元素为结尾,最长公共子序列的长度!
        int[][] com_from = new int[m+1][n+1];
        dp[0][0] = 0;
        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] + 1;
                     com_from[i][j] = 1; // 左上方来的!
                }else if(dp[i-1][j] > dp[i][j-1]){
                    dp[i][j] = dp[i-1][j];
                    com_from[i][j] = 2; // 正上方来的!
                }else {
                    dp[i][j] = dp[i][j-1];
                    com_from[i][j] = 3;// 左边来的!
                }
            }
        }
        if(dp[m][n] == 0) return "-1";
        return getAns(m,n,com_from,s1,s2);
    }
    
    private String getAns(int i,int j,int[][] com_from,String s1,String s2){
        StringBuilder ans = new StringBuilder();
        if(i == 0 || j == 0) return "";
        if(com_from[i][j] == 1){
            ans.append(getAns(i-1,j-1,com_from,s1,s2));
            ans.append(s1.charAt(i-1));
        }else if(com_from[i][j] == 2){
              ans.append(getAns(i-1,j,com_from,s1,s2));
        }else if(com_from[i][j] == 3){
              ans.append(getAns(i,j-1,com_from,s1,s2));
        }
        return ans.toString();
    }
}