描述
給定兩個字符串str1和str2汰翠，輸出兩個字符串的最長公共子序列类少。如果最長公共子序列為空，則返回"-1"封拧。目前給出的數(shù)據(jù)志鹃，僅僅會存在一個最長的公共子序列
image.png
思路：
1、定義dp[i][j] 其中dp[i][j]表示在s1中以i結(jié)尾泽西，s2中以j結(jié)尾的字符串的最長公共子序列字符串曹铃。
2、若是i位與j位的字符相等捧杉，則該問題可以變成s.charAt(i)+dp[i?1][j?1]陕见，
3、若是i位與j位的字符不相等味抖，則對比 dp[i?1][j]评甜，dp[i][j-1]誰的字符串長，就取誰的結(jié)果
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];
}
}
