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) ; } }