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

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
        int length1 = s1.length();
        int length2 = s2.length();
        
        //空字符串处理
        if(length1==0 || length2==0){
            return "-1";
        }
        
        int[][] dp = new int[length1+1][length2+1];
        
        //初始化第一列，表示空字符串与str1的最长公共子序列为0
        for(int i=0;i<length1+1;i++){
            dp[i][0] = 0;
        }
        
        //初始化第一行，表示空字符串与str2的最长公共子序列为0
        for(int i=0;i<length2+1;i++){
            dp[0][i] = 0;
        }
        
        char[] cha1 = s1.toCharArray();
        char[] cha2 = s2.toCharArray();
        String str = "";
        int length = 0;
        
        //动态规划，最优子结构，
        //状态转移方程：如果（str1[i]= str2[j]），则 dp[i+1][j+1] = dp[i][j] + 1;反之，则取c[i1,j+1] 和 c[i+1,j]的最大值
        //遍历
        for(int i=0;i<length1;i++){
            for(int j=0;j<length2;j++){
                if(cha1[i] == cha2[j]){
                    dp[i+1][j+1] = dp[i][j] + 1;
                    length++;
                }else{
                    dp[i+1][j+1] = Math.max(dp[i][j+1],dp[i+1][j]);
                }
            }
        }
        int i = length1-1;
        int j = length2-1;
        //回溯，寻找最长公共子序列
        while(i>=0 && j>=0){
          	//两个字符串末位相同
            if(cha1[i] == cha2[j]){
                str += cha1[i];
                i--;
                j--;
            }else{
              	//两个字符串末位不相同，str1字符串与str2的子串(去掉最后一位字符)存在最长公共子序列
                if(dp[i+1][j] > dp[i][j+1]){
                    j--;//字符串2（str2）下标减一
                }else{//两个字符串末位不相同，str2字符串与str1的子串(去掉最后一位字符)最长公共子序列
                    i--;//字符串1（str1）下标减一
                }
            }
        }
        String str0 = new StringBuffer(str).reverse().toString();//字符串翻转
        return length>0?str0:"-1";
    }
}