[动态规划][公共子串]最长公共子串、最长公共子序列

1、最长公共子串

LintCode：https://www.lintcode.com/problem/longest-common-substring/description
题目描述：最长公共子串
给出两个字符串，找到最长公共子串，并返回其长度。

样例
样例 1:
输入: “ABCD” and “CBCE”
输出: 2

解释:
最长公共子串是 “BC”

样例 2:
输入: “ABCD” and “EACB”
输出: 1

解释:
最长公共子串是 ‘A’ 或 ‘C’ 或 ‘B’

简要分析：按照动态规划的思路，设f[i][j]表示A字符串的前i个字符与 B字符串的前j个字符中最长公共子串。那么在求解f[i][j]时，与f[i - 1][j - 1]密切相关，如果第i个字符与第j个字符相等，那么只需要在f[i - 1][j - 1]累加该值即可。如果第i个字符与第j个字符不想等，那么公共子串从此处断掉，f[i][j] = 0。

也可以通过用类似二维表格来理解。
在这里插入图片描述

代码：

public class Solution {
    /**
     * @param A: A string
     * @param B: A string
     * @return: the length of the longest common substring.
     */
    public int longestCommonSubstring(String A, String B) {
        // write your code here
        if(A == null || A.length() == 0 || B == null || B.length() ==0)
            return 0;
        int[][] f = new int[A.length()][B.length()]; //f[i][j]表示A字符串中前i个，与B字符串中前j个的最长公共子串长度
        for(int i = 0; i < A.length(); i ++){
            for( int j = 0; j < B.length(); j ++){
                if(A.charAt(i) == B.charAt(j))
                    f[i][j] =  (i - 1 >= 0 && j - 1 >= 0) ? f[i - 1][j - 1] + 1 : 1;
            }
        }
        //遍历二维数组，寻找其中的最大值
        int maxRes = 0;
        for(int i = 0; i < A.length(); i ++){
            for( int j = 0; j < B.length(); j ++){
                if(f[i][j] > maxRes)
                    maxRes = f[i][j];
            }
        }
        return maxRes;
    }
}

2、最长公共子序列

LintCode：https://www.lintcode.com/problem/longest-common-subsequence/description

题目描述：最长公共子序列

最长公共子序列问题是在一组序列（通常2个）中找到最长公共子序列（注意：不同于子串，LCS不需要是连续的子串）。该问题是典型的计算机科学问题，是文件差异比较程序的基础，在生物信息学中也有所应用。

给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。

样例
样例 1:
输入: “ABCD” and “EDCA”
输出: 1

解释:
LCS 是 ‘A’ 或 ‘D’ 或 ‘C’

样例 2:
输入: “ABCD” and “EACB”
输出: 2

解释:
LCS 是 “AC”

简要分析：与公共子串不一样，子序列是可以不连续的。那么f[i][j]不仅仅是和f[i - 1][j - 1]存在依赖关系，其同时与f[i - 1][j]和f[i][j - 1]有关系。

如果A字符串中的第i个字符与B字符串中的第j个字符相等，可以直接在f[i - 1][j - 1]上累加。如果不相等，公共子串会直接断掉而f[i][j] = 0,子序列可以不连续，所以不需要赋值为0，只需要在当前范围的子范围内找到最大的子序列长度即可，即Math.max(f[i - 1][j],f[i][j - 1]).

代码：

public class Solution {
    /**
     * @param A: A string
     * @param B: A string
     * @return: The length of longest common subsequence of A and B
     */
    public int longestCommonSubsequence(String A, String B) {
        // write your code here
        if(A == null || A.length() == 0 || B == null || B.length() ==0 )
            return 0;
        int[][] f = new int[A.length() + 1][B.length() + 1];  //f[i][j]表示在A中到i字符串 与 B中到j位置的字符串中公共子序列的最大长度
        for(int i = 1; i <= A.length(); i ++){
            for(int j = 1; j <= B.length(); j ++){
                if(A.charAt(i - 1) == B.charAt(j - 1))
                    f[i][j]  = f[i - 1][j - 1] + 1;
                else
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
            }
        }
        return f[A.length()][B.length()];
    }
}