题解 | #最长公共子串#

设置动态规划数组dp[i][j]，表示以str1第i个字符，str2第j个字符为结尾的最长公共子串

转移方程

• 首行首列，字符相等则dp[i][j]=1，否则为0
• 其他位置，字符相等则为左上角结尾的最长公共子串长度加一，即dp[i][j]=dp[i-1][j-1]+1

在状态转移时，同时记录最长公共子串的长度和下标，最后根据结尾下标和长度返回最长公共子串

import java.util.*;

public class Solution {
    public String LCS (String str1, String str2) {
        // write code here
        int m = str1.length();
        int n = str2.length();
        if(str1==null || m==0 || str2==null || n==0) return "0";

        //记录最长公共子串的末索引位置，用str2索引
        int index = 0;
        int maxLen = 0;
        int[][] dp = new int[m][n];
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (str1.charAt(i)==str2.charAt(j)) {
                    if(i==0 || j==0){//首行，首列
                        dp[i][j] = 1;
                    }else{//其他
                        dp[i][j] = dp[i-1][j-1]+1;
                    }
                    //更新和记录最长公共子串下标
                    if(maxLen<dp[i][j]){
                        maxLen = dp[i][j];
                        index = j;
                    }
                }
            }
        }
        //结果
        if(maxLen==0) return "0";
        return str2.substring(index+1-maxLen, index+1);
    }
}