最长公共子序列

最长公共子序列（难度：中等）

题目

方法：动态规划

图1

图2

代码

code

图3

复杂度

数据复杂度：O(mn)

空间复杂度：O(mn)

---

最长公共子串

最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence）的区别： 子串要求在原字符串中是连续的，而子序列则只需保持相对顺序一致，并不要求连续。例如X = {a, Q, 1, 1}; Y = {a, 1, 1, d, f}那么，{a, 1, 1}是X和Y的最长公共子序列，但不是它们的最长公共字串。

描述：

计算两个字符串的最大公共子串（Longest Common Substring）的长度，字符不区分大小写。

方法

求子串的方法和求子序列方法类似：

1578644196190

代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n1 = text1.length();
        int n2 = text2.length();

        int dp[][] = new int[n1+1][n2+1]; //多增加一行一列
        int longest = 0;
        for(int i = 1; i <= n1; i++){
            for(int j = 1; j <= n2; j++){
                if(text1.charAt(i-1) == text2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1] + 1;
                    longest = Math.max(longest,dp[i][j]);
            }
        }
        return longest;
    }
}