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

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
        if(s1 == null || s1.length() == 0){
            return "-1";
        }
        if(s2 == null || s2.length() == 0){
            return "-1";
        }
        
        // 填dp表
        // 加一行、加一列,方便赋值. 默认初始值为0
        int[][] dp = new int[s1.length()+1][s2.length()+1];
        for (int i = 1;i < dp.length;i++){
            char c1 = s1.charAt(i-1);
            for(int j = 1;j < dp[0].length;j++){
                if(c1 == s2.charAt(j-1)){   // 相等,=左上角 + 1
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);  // 不等,=max(左边,上边)
                }
            }
        }
        
        int i = dp.length - 1;
        int j = dp[0].length - 1;
        if(dp[i][j] == 0){
            return "-1";
        }
        // 查找最长公共子序列.  从右下角开始找
        StringBuilder stb = new StringBuilder();
        while(i >= 1 && j >= 1){
           if(dp[i][j] > dp[i-1][j] && dp[i][j] > dp[i][j-1]){  // 当时填表选择的时候,两个字符串相等,选择的是左上角的,那当前字符一定属于答案
               stb.append(s1.charAt(i-1));
               i--;
               j--;
           }else if(dp[i][j] > dp[i][j-1]){   // 比左边值大,说明当时选择的是上方
               i--; 
           }else{
               j--;
           }
        }
        return stb.reverse().toString();
    }
}