题解 | #最长公共子串-动态规划#

动态规划

对于字符串str1（长度为m）和str2(长度为n)，我们可以使用一个二维整形数组(m * n)实现动态规划算法。

思路：
dp[i][j]：表示在str1中以坐标i结尾的子串与str2中以坐标j结尾的子串，最长公共子串的长度（从i，j的位置往前推）

递推方程：

• 如果str1第i个字符不等于str2第j个字符，那么dp[i][j] = 0
• 否则 dp[i][j] = dp[i-1][j-1] + 1

关于字符串的截取：
使用一个整型变量maxLength来记录当前的最长公共子串的长度
使用一个整型变量lastIndex来指向str1中当前最长公共子串的最后一个字符的下标

import java.util.*;

public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m][n];
        int maxLength = 0;

        //用来记录str1中最长公共串的最后一个字符的下标
        int lastIndex = 0;     
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){

                //判断str1中第i个字符是否和str2中第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(dp[i][j] > maxLength){    
                        maxLength = dp[i][j];
                        lastIndex = i;
                    }
                }
            }
        }

        //通过str1来截取长度为maxLength, 最后字符坐标为lastIndex的子串
        return str1.substring(lastIndex - maxLength + 1, lastIndex + 1);     
    }
}