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

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) {

        s1 = " " + s1;
        s2 = " " + s2;

        int len1 = s1.length();
        int len2 = s2.length();

        String[][] dp = new String[len1][len2];

        //初始化""
        for (int i = 0; i < len1; i++) {
            dp[i][0] = "";
        }
        for (int i = 0; i < len2; i++) {
            dp[0][i] = "";
        }

        // 填充dp表
        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                // 匹配到相同的，就添加到dp中
                if (s1.charAt(i) == s2.charAt(j)) { 
                    dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i);
                } else {
                    dp[i][j] = dp[i - 1][j].length() > dp[i][j - 1].length() ? dp[i - 1][j] : dp[i][j - 1];
                }
            }
        }


        if (dp[len1 - 1][len2 - 1] == null || dp[len1 - 1][len2 - 1] == "") {
            return "-1";
        }
        return  dp[len1 - 1][len2 - 1];
    }
}


/**  // 空间性能优化，但不易理解
public String LCS(String s1, String s2) {
    // 边界检查
    if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
        return "-1";
    }

    int len1 = s1.length();
    int len2 = s2.length();

    // dp[i][j] 表示 s1 前 i 个字符和 s2 前 j 个字符的 LCS 长度
    int[][] dp = new int[len1 + 1][len2 + 1];

    // 填充 dp 表
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                // 字符匹配，LCS 长度加 1
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // 字符不匹配，取上方或左方的最大值
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // 如果 LCS 长度为 0，返回 -1
    if (dp[len1][len2] == 0) {
        return "-1";
    }

    // 通过 dp 表反向推导 LCS 字符串
    StringBuilder lcs = new StringBuilder();
    int i = len1, j = len2;
    while (i > 0 && j > 0) {
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            // 字符匹配，加入 LCS
            lcs.append(s1.charAt(i - 1));
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            // 上方值更大，向上移动
            i--;
        } else {
            // 左方值更大，向左移动
            j--;
        }
    }

    // 反转字符串得到正确的 LCS
    return lcs.reverse().toString();
} */