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

（算法思路详见《算法导论（第3版）》15.4 最长公共子序列 ）

public class Solution {
    private static final String EMPTY = "-1";
    private String currLCS = "";
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        if (s1 == null || s1.isEmpty() || s2 == null || s2.isEmpty()) return EMPTY;

        int[][] c = new int[s1.length()+1][s2.length()+1];


        StringBuilder rsb = new StringBuilder();

        LCSLength(s1.toCharArray(),s2.toCharArray(),c);
        LCSPrint(c,s1.length(),s2.length(),rsb,s1.toCharArray(),s2.toCharArray());

        if (rsb.length() == 0) return EMPTY;
        return rsb.toString();
    }

    private void LCSPrint(int[][] c, int i, int j, StringBuilder rsb, char[] x, char[] y) {
        if (i == 0 || j == 0) return;

        if (x[i - 1] == y[j - 1]){
            LCSPrint(c,i-1,j-1,rsb,x,y);
            rsb.append(x[i-1]);
        }
        else if(c[i - 1][j] >= c[i][j - 1]){
            LCSPrint(c,i-1,j,rsb,x,y);
        }
        else {
            LCSPrint(c,i,j-1,rsb,x,y);
        }
    }

    private void LCSLength(char[] x, char[] y, int[][] c) {
        for (int i = 0,j = 1; j < c[0].length; j++) {
            c[i][j] = 0;
        }
        for (int i = 1,j = 0; i < c.length; i++) {
            c[i][j] = 0;
        }

        for (int i = 1;i < c.length; i++) {
            for (int j = 1; j < c[0].length; j++) {
                if (x[i - 1] == y[j - 1]){
                    c[i][j] = c[i - 1][j - 1]+1;
                }
                else if(c[i - 1][j] >= c[i][j - 1]){
                    c[i][j] = c[i - 1][j];
                }
                else {
                    c[i][j] = c[i][j - 1];
                }
            }
        }
    }

}