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 m = s1.length();
int n = s2.length();
if(m==0||n==0){
return "-1";
}
String[][] dp = new String[m+1][n+1];
for(int i = 0;i<=m;i++){
dp[i][0] = "";
}
for(int j = 0;j<=n;j++){
dp[0][j] = "";
}
for(int i = 1;i<=m;i++){
for(int j = 1;j<=n;j++){
if(s1.charAt(i-1) == s2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1]+s1.charAt(i-1);
}else{
if(dp[i-1][j].length() > dp[i][j-1].length()){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = dp[i][j-1];
}
}
}
}
if(dp[m][n].equals("")){
return "-1";
}
return dp[m][n];
}
}