题解 | #最长公共子序列-II#

package org.example.test;

public class LCSTest {
    public static void main(String[] args) {
        System.out.println(LCS("1a1a31", "1a231"));
    }

    /**
     * dp[i][j] 数组存放两个字符串s1[i]到s2[j]最长公共字符串。
     *
     * @param s1
     * @param s2
     * @return
     */
    public static String LCS(String s1, String s2) {
        // write code here
        int a = s1.length();
        int b = s2.length();
        String[][] dp = new String[a + 1][b + 1];
        for (int i = 0; i <= b; i++) {
            dp[0][i] = "";
        }
        for (int i = 0; i <= a; i++) {
            dp[i][0] = "";
        }

        for (int i = 1; i <= a; i++) {
            char c1 = s1.charAt(i - 1);
            for (int j = 1; j <= b; j++) {
                char c2 = s2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + c2;
                } else {
                    if (dp[i - 1][j].length() > dp[i][j - 1].length()) {
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i][j - 1];
                    }
                }
            }
        }
        return dp[a][b].equals("") ? "-1" : dp[a][b];
    }
}