DP四大问题总结之最长公共子序,公共子串

Dynamic Programming

Posted by Jerry on February 24, 2017

找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。子串是特殊的子序。

最长公共子序(Longest common subsequence)

问题描述

给定两个字符串,s="snowhappy"r="nowaday",求公共子序,子序在于不要求序列为在原字符串中连续,本案例中,最长公共子序为noway,长度为5。 对于目串$X = < x_1, x_2, \cdots , x_m >$, $Y = < y_1, y_2, \cdots , y_m >$,求LCS

求解算法

  1. 暴力解法:假设m<n, 对于母串X,我们可以暴力找出2m个子序列,然后依次在母串Y中匹配,算法的时间复杂度会达到指数级$O(n*2^m)$。显然,暴力求解不太适用于此类问题。
  2. DP解法:假设$Z =< z_1, z_2, \cdots , z_k >$是X与Y的LCS,注意到 如果$x_m = y_m$,则$z_k = x_m = y_m$,有$Z_{k-1}$是$X_{m-1}$与$y_{m-1}$的LCS 如果$x_m \ne y_m$,则$Z_{k}$是$X_{m}$与$y_{m-1}$的LCS,或者是$X_{m-1}$与$y_{m}$的LCS 因此,求解LCS的问题则变成递归求解的两个子问题。但是,上述的递归求解的办法中,重复的子问题多,效率低下。改进的办法用空间换时间,用数组保存中间状态,方便后面的计算。这就是动态规划(DP)的核心思想。时间复杂度O(n^2),空间复杂度O(n^2)

用二维数组dp[i][j]记录串$x_1x_2 \cdots x_i$与$y_1y_2\cdots y_j$的LCS长度,则可得到状态转移方程

lcs

ps.正在学习MathJax

代码实现

class Solution{
    public int LCS(String s1, String s2){
        if(s1==null||s2==null||s1.length()==0||s2.length()==0){
            return 0;
        }
        //注意dp长度为字符串长度+1,方便统一i=0和j=0的情况,不用分类讨论了
        int[][] dp = new int[s1.length()+1][s2.length()+1];
        //i取值可以去到len(i)的长度
        for(int i=0;i<=s1.length();i++){
            for (int j = 0;j<=s2.length();j++){
                if(i==0||j==0){
                    dp[i][j] = 0;
                }
                else if(s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1] + 1;
                }else{
                    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }

        //逆序打印LCS
        for(int i = s1.length(),j=s2.length();i>=1&&j>=1;){
            if(s1.charAt(i-1)==s2.charAt(j-1)){
                System.out.print(s1.charAt(i-1));
                i--;j--;
            }else if(dp[i][j-1]>=dp[i-1][j]){
                j--;
            }else {
                i--;
            }
        }
        System.out.println();
        return dp[s1.length()][s2.length()];
    }
}

最长公共子串 (Longest common substring)

问题描述

求两个字符串,最长公共连续子串

求解算法

暴力解法与公共子序一样的时间复杂度。 前面提到了子串是一种特殊的子序列,因此同样可以用DP来解决。定义数组的存储含义对于后面推导转移方程显得尤为重要,糟糕的数组定义会导致异常繁杂的转移方程。 状态转移方程式: lcsubString

代码实现

//如果要打印LCS只需要找到dp[][]数组中最大的元素,然后依次i--,j--,对角线>0的打印出来即可
class Solution{
    public int LCSubstring(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
            return 0;
        }
        //注意dp长度为字符串长度+1,方便统一i=0和j=0的情况,不用分类讨论了
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        //记录最大长度
        int res = 0;
        //i取值可以取到len(i)的长度
        for (int i = 0; i <= s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                } else if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    res = Math.max(dp[i][j], res);
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return res;
    }
}

参考资料

  1. http://www.cnblogs.com/en-heng/p/3963803.html