题解 | #打印最长公共子序列#

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) {
        if(s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) return "-1" ;
        char[] arr1 = s1.toCharArray() ;
        char[] arr2 = s2.toCharArray() ;
        int len1 = arr1.length ;
        int len2 = arr2.length ;
        //dp[i][j]表示arr1前i个字符和arr2的前j个字符的最长公共子序列的长度
        int[][] dp = new int[len1 + 1][len2 + 1] ;
        //面对arr1前i个字符和arr2的前j个字符时要得到最长公共子序列的选择
        int[][] pai = new int[len1 + 1][len2 + 1] ;
        for(int i = 0 ; i <= len1 ; i ++) {
            for(int j = 0 ; j <= len2 ; j ++) {
                if(j == 0 || i == 0) {
                    dp[i][j] = 0 ;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i][j-1]) ;
                    if(dp[i][j] == dp[i-1][j]) {
                        pai[i][j] = 1 ;//选择了dp[i-1][j]
                    } else {
                        pai[i][j] = 2 ;//选择了dp[i][j-1]
                    }
                    if(arr1[i-1] == arr2[j-1]) {
                        dp[i][j] = Math.max(dp[i][j] , dp[i-1][j-1] + 1) ; 
                        if(dp[i][j] == dp[i-1][j-1] + 1) {
                            pai[i][j] = 3 ;//选择了dp[i-1][j-1]
                        }
                    }
                }
            }
        }
        int maxLen = dp[len1][len2] ;
        if (maxLen == 0) return "-1" ;
        char[] res = new char[maxLen] ;//存储最长公共子序列
        int p = maxLen - 1 ;
        int i = len1 ;
        int j = len2 ;
        while(i > 0 && j > 0) {
            if(pai[i][j] == 1) {
                i -- ;
            } else if(pai[i][j] == 2) {
                j -- ;
            } else {
                res[p--] = arr1[i - 1] ;
                i -- ;
                j -- ;
            }
        }
        return new String(res) ;
    }
}