题解 | #最长公共子串#

两个字符串的最长公共子串和最长公共子序列

最长公共子串

最长公共子序列

//最长公共子串
public class Solution {
    public String LCS (String str1, String str2) {
        int m=str1.length();
        int n=str2.length();
        int[][] dp=new int[m+1][n+1];
        int tail_index=0;
        int maxlen=0;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                if(dp[i][j]>maxlen){
                    maxlen=dp[i][j];
                    tail_index=i;
                }
            }
        }
        return str1.substring(tail_index-maxlen,tail_index);

    }
}

//最长公共子序列
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m=text1.length();
        int n=text2.length();
        int[][] dp=new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(text1.charAt(i-1)==text2.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]);
                }
            }
        }
        return dp[m][n];

    }
}