题解-通俗易懂 | Java-二维DP-#最长公共子序列-II#

二维DP

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) {
        // write code here
        char[] cc1 = s1.toCharArray();
        char[] cc2 = s2.toCharArray();
        int n1 = cc1.length;
        int n2 = cc2.length;
        String dps[][] = new String[n1 + 1][n2 + 1];
        Arrays.fill(dps[0], "");
        for (int i = 0; i <= n1; ++i) {
            dps[i][0] = "";
        }
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (cc1[i - 1] == cc2[j - 1]) {
                    dps[i][j] = dps[i - 1][j - 1] + cc1[i - 1];
                } else if (dps[i - 1][j].length() > dps[i][j - 1].length()) {
                    dps[i][j] = dps[i - 1][j];
                } else {
                    dps[i][j] = dps[i][j - 1];
                }
            }
        }
        return dps[n1][n2].length() == 0 ? "-1" : dps[n1][n2];
    }
}