1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public String LCS(String s1, String s2) {
    if(s1==null||s2==null||s1.length()==0||s2.length()==0){
        return "-1";
    }

    int m = s1.length();
    int n = s2.length();
    String[][] dp = new String[m+1][n+1];
    
    // 把所有dp[0][j] 和 dp[i][0] 赋值为空字符串 ""，解决null问题
    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{
                String temp1String = dp[i-1][j];
                String temp2String = dp[i][j-1];
                dp[i][j]=temp1String.length()>temp2String.length()?temp1String:temp2String;
            }
        }
    }
    
    String res = dp[m][n];
    return res.length()>0 ? res : "-1";
}