描述
给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列
image.png
思路：
1、定义dp[i][j] 其中dp[i][j]表示在s1中以i结尾，s2中以j结尾的字符串的最长公共子序列字符串。
2、若是i位与j位的字符相等，则该问题可以变成s.charAt(i)+dp[i−1][j−1]，
3、若是i位与j位的字符不相等，则对比 dp[i−1][j]，dp[i][j-1]谁的字符串长，就取谁的结果
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) {
int length1 =s1.length();
int length2 =s2.length();
String[][]dp=new String[length1+1][length2+1];
for(int i = 0;i<=length1;i++){
for(int j = 0;j<=length2;j++){
if(i == 0||j==0){dp[i][j] = "";}
else 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[length1][length2]=="") return "-1";
return dp[length1][length2];
}
}
