动态规划经典题：给出两个字符串s1和s2，返回其中最大的公共子串

╰+攻爆jí腚メ 2024-02-18 14:32 8阅读 0赞

## 求公共子字符串问题（连续的） ##

这个题目是当时远景能源公司现场笔试的一道题目，当时根本就不知道动态规划是什么鬼，直接上来就暴力求解，面试官很谄媚的问我，你这能求出来吗？当时很年轻的说，能啊！现在想，当时哪来的自信和逗比勇气说这大话。。。在《进军硅谷》这本书上看到原题，我是懵逼，怎么想出这种解答出来的，下面直接上思路和代码。

### 思路： ###

定义二维数组dp\[i\]\[j\]记录最大公共子串的长度,  
\* 若要返回字符串可以用s1.substring(i-dp\[i\]\[j\]+1, i+1)  
\* 当s\[i\]==s\[j\]时，dp\[i\]\[j\]=dp\[i-1\]\[j-1\]+1;  
\* 当s\[i\]!=s\[j\]时，dp\[i\]\[j\]=0;

> 有点类似于数学归纳法

### 方案： ###

*  首先考虑空或者长度为0的情况，直接返回”“；
 *  然后进入双重循环：
 *  1.利用charAt(int index)方法来比较两个字符串相等的时机
 *  2.考虑边界情况，两个字符串中有一个是起始为0就相等，则dp\[i\]\[j\]=1
 *  3.除了边界情况，其他最大字符串长度为dp\[i\]\[j\]=dp\[i-1\]\[j-1\]+1;
 *  4.不断的替换掉最大的长度并返回公共子串
 *  最后循环结束后，返回最大的公共子串

public static String maxCommonString(String s1, String s2) {
            String res = "";
            if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0)
                return res;
            int max = 0, m = s1.length(), n = s2.length();
            int[][] dp = new int[m][n]; // 定义一个二维数组记录最大公共子串的长度
            // 计算到s1的第i个字符和s2的第j个字符为止的最大公共子串长度
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 如果s1字符串在i处和s2字符串在j处有字符相同，进入if代码块中
                    if (s1.charAt(i) == s2.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] > max) {
                            max = dp[i][j];
                            res = s1.substring(i - dp[i][j] + 1, i + 1);// substring()左闭右开
                        }
                    }
                }
            }
            return res;
        }

### 动态规划介绍 ###

动态规划算法一般是基于一个递推公式（如上面的当s\[i\]==s\[j\]时，dp\[i\]\[j\]=dp\[i-1\]\[j-1\]+1;）以及一个或多个初始状态（当s\[i\]!=s\[j\]时，dp\[i\]\[j\]=0;），当前子问题其实是由上一次子问题的解推算出来的。  
【附带福利：markdown每行缩进的方式】

> 半方的空白&ensp；或&\#8194；  
> 全方的空白&emsp；或&\#8195；  
> 不断行的空白格&nbsp；或&\#160；  
> (分号都是英文格式的)