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

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) {
        // 特殊情况
        if (s1.length() == 0 || s2.length() == 0) {
            return "-1";
        }

        int len1 = s1.length();
        int len2 = s2.length();
        // dp[i][j]表示第一个字符串到第i位，第二个字符串到第j位为止的最长公共子序列长度
        // 初始化-1
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        // 子序列的拼接方式 - 1表示来自左上（i-1, j-1）、2表示来自左（i-1, j）、3表示来自上（i, j-1）
        int[][] from = new int[len1 + 1][len2 + 1];

        // 首先获取最长子序列的最大长度，并填写from表格（用于得到子序列）
        int length = process1(s1, s2, len1, len2, dp, from);

        // 根据from表格，获取答案字符串
        String res = process2(s1, s2, len1, len2, from);

        // 检查答案是否位空
        if (res.isEmpty()) {
            return "-1";
        } else {
            return res;
        }
    }

    // 记忆化搜索
    // 获取最长公共子序列长度并填写from表
    public int process1 (String s1, String s2, int i, int j, int[][] dp,
                         int[][] from) {
        // 递归出口
        if (i == 0 || j == 0) {
            dp[i][j] = 0;
            return dp[i][j];
        }

        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        // 递归分支
        // 遇到两个字符相等，则无论[i-1][j-1]的最长公共子序列是什么情况，该字符都会令其长度+1
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            // 情况等同于dp[i-1][j-1] + 1（加上该公共字符）
            if (dp[i - 1][j - 1] == -1) {
                dp[i - 1][j - 1] = process1(s1, s2, i - 1, j - 1, dp, from);
            }
            dp[i][j] = dp[i - 1][j - 1] + 1;
            // 来自左上方
            from[i][j] = 1;
        } else {
            // 遇到的两个字符不同，则该字符必然不会进入公共子序列
            // [i][j]的情况就是[i-1][j-1]、[i][j-1]和[i-1][j]中的最大值
            // 易证，[i-1][j-1]的情况一定不会大于后面两种，因此只比较[i][j-1]和[i-1][j]即可
            // 左边的选择更大，即第一个字符串后退一位
            if (dp[i - 1][j] == -1) {
                dp[i - 1][j] = process1(s1, s2, i - 1, j, dp, from);
            }
            if (dp[i][j - 1] == -1) {
                dp[i][j - 1] = process1(s1, s2, i, j - 1, dp, from);
            }
            if (dp[i - 1][j] > dp[i][j - 1]) {
                dp[i][j] = dp[i - 1][j];
                //来自于左方
                from[i][j] = 2;
            }
            // 右边的选择更大，即第二个字符串后退一位
            else {
                dp[i][j] = dp[i][j - 1];
                // 来自于上方
                from[i][j] = 3;
            }
        }
        return dp[i][j];
    }

    // 递归获取最长公共子序列
    public String process2 (String s1, String s2, int i, int j, int[][] from) {
        String res = "";
        // 递归出口
        if (i == 0 || j == 0) {
            return "";
        }
        
        // 根据方向，往前递归，然后添加本级字符
        if (from[i][j] == 1) {
            res = process2(s1, s2, i - 1, j - 1, from) + s1.charAt(i - 1);
        } else if (from[i][j] == 2) {
            res = process2(s1, s2, i - 1, j, from);
        } else if (from[i][j] == 3) {
            res = process2(s1, s2, i, j - 1, from);
        }
        return res;
    }
}