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

import java.util.*;
public class Solution {
    /**
     * 定义 dp[i][j] 表示 str1前 i 个字符 和 str2前 j 个字符的公共子序列长度
     * 分解：1. str1[i] = str2[j] 的情况，即 dp[i][j] = dp[i - 1][j - 1] + 1
     * 2. str1[i] != str2[j] 的情况，即 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
     * 然后回溯子序列，从两个串的最后一个字符开始
     * 如果 str1[i] = str2[j]，则包含在子序列里，向左上角移动
     * 如果 str1[i] ！= str2[j]，则不包含在子序列里，向左或者向上移动，哪个大就向哪个移动
     */
    public String LCS(String str1, String str2) {
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        int len1 = str1.length(), len2 = str2.length();
        while (len1 > 0 && len2 > 0) {
            if (str1.charAt(len1 - 1) == str2.charAt(len2 - 1)) {
                sb.append(str1.charAt(len1 - 1));
                len1--;
                len2--;
            } else {
                if (dp[len1 - 1][len2] > dp[len1][len2 - 1]) {
                    len1--;
                } else {
                    len2--;
                }
            }
        }
        if (sb.length() == 0) {
            return "-1";
        }
        return sb.reverse().toString();
    }
}