题解 | #最长公共子序列(二)#

public String LCS (String s1, String s2) {
        // write code here
        int m=s1.length();
        int n=s2.length();
        int[][] dp=new int[m+1][n+1];
        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]+1;
                else
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        StringBuffer ss=new StringBuffer();
        int row=m,col=n;
        while(row>0&&col>0){
            while (row>0&&dp[row][col]==dp[row-1][col])
                row--;
            while(col>0&&dp[row][col]==dp[row][col-1])
                col--;
            if(row>0)
                ss.append(s1.charAt(row-1));
            row--;
            col--;
        }
        if(ss.length()==0)
            return "-1";
        return ss.reverse().toString();
    }