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

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 || s2 ==null || s1.length() == 0 || s2.length() == 0) { return "-1"; } char[] char1 = s1.toCharArray(); char[] char2 = s2.toCharArray(); int[][] dp = dp(char1,char2); int m = char1.length-1; int n = char2.length-1; char[] res = new char[dp[m][n]]; int index = res.length - 1;

    while(index >= 0) {
        if(n>0 && dp[m][n] == dp[m][n-1]) {
            n--;
        }else if(m>0 &&dp[m-1][n] == dp[m][n]) {
            m--;
        }else {
            res[index--] = char1[m];
            m--;
            n--;
        }
    }
    String resStr = String.valueOf(res);
    return resStr.equals("")? "-1" : resStr;
}

public int[][] dp(char[] char1, char[] char2) {
    int[][] dp = new int[char1.length][char2.length];
    
    dp[0][0] = char1[0] == char2[0] ? 1 : 0;
    
    for(int i = 1;i<char1.length;i++) {
        dp[i][0] = Math.max(dp[i-1][0], char1[i] == char2[0] ? 1 : 0);
    }
    for(int i = 1;i<char2.length;i++) {
        dp[0][i] = Math.max(dp[0][i-1], char1[0] == char2[i] ? 1 : 0);
    }
    
    for(int i = 1;i<char1.length;i++) {
        for(int j = 1;j<char2.length;j++) {
            int max = Math.max(dp[i-1][j],dp[i][j-1]);
            if(char1[i] == char2[j]){
                max = Math.max(dp[i-1][j-1]+1, max);
            }
            dp[i][j] = max;
        }
    }
    return dp;
}

}