题目描述

给定两个字符串str1和str2，输出连个字符串的最长公共子序列。如过最长公共子序列为空，则输出-1。

示例1

输入
"1A2C3D4B56","B1D23CA45B6A"
返回值
"123456"
说明
"123456"和“12C4B6”都是最长公共子序列，任意输出一个。

思路

1. Q1：dp数组设置？
   两个字符串比较，设置dp[m+1][n+1],dp[i][j]表示字符串1[:i]和字符串2[:j]比较的结果
2. Q2:状态转移方程？
   一开始写成dp[i][j]=dp[i-1][j-1]+chs1[i-1]==chs2[j-1]?1:0;结果不对。
   后来想到，如果不等的话，应该和dp[i][j-1],dp[i-1][j]有关.

code

import java.util.*;
public class Solution {
    public String LCS (String s1, String s2) {
        char []chs1=s1.toCharArray();
        char []chs2=s2.toCharArray();
        int m=chs1.length,n=chs2.length;
        if(m==0||n==0)return "-1";
        int dp[][]=new int[m+1][n+1];
        int max=-1;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(chs1[i-1]==chs2[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]);
                max = Math.max(max,dp[i][j]);
            }
        }
        int i=m,j=n;
        StringBuffer sb = new StringBuffer();
        while(i!=0&&j!=0){
            if(chs1[i-1]==chs2[j-1]){
                sb.append(chs1[i-1]);
                i--;j--;
            }else{
                int temp = dp[i-1][j]>dp[i][j-1]?i--:j--; //temp无用，只为简洁
            }
        }
        if(sb.length() == 0)
            return "-1";
        return sb.reverse().toString();
    }
}