描述

給定兩個字符串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];
    }
}