求公共子字符串难题(一而再的)

其一题目是即时远景能源公司实地笔试的一道标题,当时一向就不晓得动态规划是何等鬼,直接上来就武力求解,面试官很谄媚的问笔者,你这能求出来呢?当时很年轻的说,能啊!未来想,当时哪来的自信和逗比勇气说那大话。。。在《进军硅谷》那本书上看到原题,笔者是懵逼,怎么想出这种解答出来的,上边直接上思路和代码。

思路:

概念二维数组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;),当前子难题莫过于是由上1次子题材的解推算出来的。
【附带福利:markdown每行缩进的方法】

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

网站地图xml地图