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

import java.util.*;

public class Solution { /** * longest common subsequence * @param s1 string字符串 the string * @param s2 string字符串 the string * @return string字符串 */

String dfs( String s1,String s2,int dp[][],int i,int j ){//反推(i,j)这个状态是哪个状态变过来的
    
    if( i==0 ||j==0 ) return "";
    
    if( s1.charAt(i-1)==s2.charAt(j-1) ){//如果i，j对应的字符相等，（i，j）肯定是（i-1，j-1）变过来的
        return dfs( s1,s2,dp,i-1,j-1 )+s1.charAt(i-1);
    }else{
        if( dp[i-1][j]>dp[i][j-1] ){//否则，看看我们之前的数组，（i，j）是哪个位置变过来的
            return dfs( s1,s2,dp,i-1,j );
        }else{
            return dfs( s1,s2,dp,i,j-1 );
        }
    }
}

public String LCS (String s1, String s2) {
    // write code here
    
    int n=s1.length();
    int m=s2.length();
    int dp[][]=new int [n+5][m+5];
    for( int i=1;i<=n;i++ ){
        
        for(int j=1;j<=m;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]);
            }
        }
    }
    String ans=dfs(s1,s2,dp,n,m);
    if( ans=="" ) return "-1";
    return ans;
}

}