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

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) {
        char[] chs1 = s1.toCharArray();
        char[] chs2 = s2.toCharArray();
        int m = chs1.length, n = chs2.length;
        if (m == 0 || n == 0) {
            return "-1";
        }
        //f[i][j]表示第一个字符串以第i个字符结尾，第二个字符串以第j个字符串结尾的最长公共子序列长度
        int[][] f = new int[m + 1][n + 1];
        /*
         * 状态转移方程：
         *   f[i][j] = f[i-1][j-1]+1  a[i] = b[j]
         *   f[i][j] = max{ f[i-1][j], f[i][j-1] } a[i] != b[j]
         * 边界条件：
         *   f[0][j] = f[i][0] = 0
         */
        int i, j = 0;
        //根据状态转移方程，计算最长公共子序列的值
        for (i = 1; i <= m; i++) {
            for (j = 1; j <= n; j++) {
                if (chs1[i - 1] == chs2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        //没有公共子序列
        if (f[m][n] == 0) {
            return "-1";
        }
        i = m;
        j = n;
        String str = "";
        while (i > 0 && j > 0) {
            //当前末尾元素为公共子序列的值
            if (chs1[i - 1] == chs2[j - 1]) {
                str = chs1[i - 1] + str;
                i--;
                j--;
                //哪个元素大向哪块移动
            } else if (f[i][j - 1] > f[i - 1][j]) {
                j--;
            } else {
                i--;
            }
        }
        return str;
    }
}