<dp>求最长的公共子串

300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note:

  • There may be more than one LIS combination, it is only necessary for you to return the length.
  • Your algorithm should run in O(n2) complexity.

题目大意:一个数组的最长上升子序列。

思路:这是一个动态规划问题,array[i]表示以array[i]为结尾的最长上升子序列的长度。动态回话方程:

array[i]= Math.max(array[i],1+array[j]);

解法:

     public int lengthOfLIS(int[] nums) {
        if(nums == null|| nums.length ==0) return 0;
        int [] array = new int[nums.length];
        for (int i=0;i<array.length;i++){
            array[i] = 1;
        }

        // array[i]表示以array[i]为结尾的最长上升子序列的长度。
        for (int i = 1;i<nums.length;i++){
            for (int j = 0;j<i;j++){
                if (nums[j] < nums[i]){
                    array[i] = Math.max(array[i],1+array[j]);
                }
            }
        }

        int res = 1;
        for (int i = 0;i<array.length;i++){
            res = Math.max(res,array[i]);
        }
        return res;
    }

二.求最长的公共子串

给定两个字符串str1和str2,返回两个字符串的最长公共子串

例如:str1 = "1AB2345CD",str2 = "12345EF"

最长的子串是“2345”

解法一:

这是一个基本的动态规划解法,时间复杂度是O(N*M),空间复杂度是O(N*M);

public static int [][] longestSubString(String str1,String str2){
    char [] chars1 = str1.toCharArray();
    char [] chars2 = str2.toCharArray();
    int [][] dp = new int[chars1.length][chars2.length];
    for (int i=0;i<str1.length();i++){
        if (chars2[0] == chars1[i]){
            dp[i][0] = 1;
        }
    }

    for (int j = 1;j<str2.length();j++){
        if (chars1[0] == chars2[j]){
            dp[0][j] = 1;
        }
    }

    for (int i = 1;i<chars1.length;i++){
        for (int j = 1;j<chars2.length;j++){
            if (chars1[i] == chars2[j]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }
        }
    }
    return dp;
}

public static String lcst1(String str1,String str2){
    if (str1==null||str2==null||str1.equals("")||str2.equals("")){
        return "";
    }
    int[][] dp = longestSubString(str1,str2);
    int end = 0;
    int max = 0;
    for (int i = 0;i<str1.length();i++){
        for (int j = 0;j<str2.length();j++){
            if (dp[i][j]>max){
                end = i;
                max = dp[i][j];
            }
        }
    }
    return str1.substring(end-max+1,end+1);
}

longestSubString()函数获取dp数组:

1 0 0 0 0 0 0 
0 0 0 0 0 0 0 
0 0 0 0 0 0 0 
0 1 0 0 0 0 0 
0 0 2 0 0 0 0 
0 0 0 3 0 0 0 
0 0 0 0 4 0 0 
0 0 0 0 0 0 0 
0 0 0 0 0 0 0 

可以发现,最长的子数组长度是4,end变量找到合适的位置,然后取4个长度的字符串的长度即可。

解法二:

这是一个改进的方式,时间复杂度是O(N*M),空间复杂度是O(1);

三.求最长的公共子序列

给定两个字符串str1和str2,返回两个字符串的最长公共子序列。

例如:str1 = "1A2C3D4B56" str2 = "B1D23CA45B6A"

"123456"或"12C4B6",都是最长的公共子序列。

思路:LCS(m,n) 是S1[0...m]和S2[0...n]的最长公共子序列的长度

那么存在两种情况:(从末尾到头)

S1[m] == S2[n],则有:LCS(m,n) = 1 +LCS(m-1,n-1)

S1[m] != S2[n],则有:LCS(m,n) =max(LCS(m-1,n),LCS(m,n-1))

求出公共子序列的长度如下:

public int LCS(String str1, String str2){
    int[][] dp = new int[str1.length()+1][str2.length()+1];
    for (int i = 1 ;i<=str1.length();i++){
        for (int j = 1;j<=str2.length();j++){
            if (str1.charAt(i-1) == str2.charAt(j-1)){
                dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+1);
            }
            else{
                dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
            }
        }
    }
    return dp[str1.length()][str2.length()];
}

假设:

String str1 = "13456778";
String str2 = "357486782";

那么dp二维数组的输出如下:注意这里的dp定义的是(m+1)*(n+1)的,所以首行首列都是0

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 1 1 1 1 1 1 1 1 1 
0 1 1 1 2 2 2 2 2 2 
0 1 2 2 2 2 2  2 2 
0 1 2 2 2 2 3 3 3 3 
0 1 2 3 3 3 3 4 4 4 
0 1 2 3 3 3 3 4 4 4 
0 1 2 3 3 4 4 4 5 5 

现在仅仅求出的是公共子序列的长度,那么怎样才能将公共子序列求出来呢??

  1. S1[i] != S2[j] ,且dp[i-1][j] = dp[i][j-1] 这种存在分支的情况,这里请都选择一个方向(之后遇到这样的情况,也选择相同的方向)
  2. 如果s1[i] == s2[j] 就跳转到dp[i - 1][j - 1],如果s1[i] != s1[j], 就向前找或向上找(只能一个方向)

代码实现如下所示:

    int i = str1.length();
    int j = str2.length();
    while (i>0 && j>0){
        if (str1.charAt(i-1) != str2.charAt(j-1)){
            if (dp[i][j-1]>dp[i-1][j]){
                j--;
            }else{
                i--;
            }
        } else {     //S1[i] == S2[j],  c[i - 1][j - 1]
            result += str1.charAt(i-1);
            i--;
            j--;
        }

    }
    return result;
}

那么完整的求最长的公共子序列的代码如下

public String LCS(String str1, String str2){
    String result = "";
    int[][] dp = new int[str1.length()+1][str2.length()+1];
    for (int i = 1 ;i<=str1.length();i++){
        for (int j = 1;j<=str2.length();j++){
            if (str1.charAt(i-1) == str2.charAt(j-1)){
                dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+1);
            }
            else{
                dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
            }
        }
    }
    int i = str1.length();
    int j = str2.length();
    while (i>0 && j>0){
        if (str1.charAt(i-1) != str2.charAt(j-1)){
            if (dp[i][j-1]>dp[i-1][j]){
                j--;
            }else{
                i--;
            }
        } else {     //S1[i] == S2[j],  c[i - 1][j - 1]
            result += str1.charAt(i-1);
            i--;
            j--;
        }

    }
    return result;
}

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python学习路

四、正则表达式re模块 常用的匹配规则:Python 的 re 模块也可以直接用re.match(),re.search(),re.findall(),re.finditer(),re.sub()

什么是正则表达式 正则表达式,又称规则表达式,通常被用来检索、替换那些符合某个模式(规则)的文本。 正则表达式是对字符串操作的一种逻辑公式,就是用事先定义好...

40040
来自专栏JavaEdge

Java中正则表达式PatternMatcherStringJava String.split()用法小结

31450
来自专栏海天一树

小朋友学C语言(5):常量和变量

先动手编写程序: #include <stdio.h> int main() { int a = 1; printf("a = %d\n", a...

35690
来自专栏浪淘沙

实训day03--循环,内存,数组

2018.06.06 1.switch用法 Scanner sc = new Scanner(System.in); while(t...

13630
来自专栏章鱼的慢慢技术路

LeetCode_1. Two Sum_Solution

这道题目的意思是给定一个数组和一个值,要求出这个数组中两个值的和等于这个给定值target。

12830
来自专栏深度学习之tensorflow实战篇

递归与伪递归区别,Python 实现递归与尾递归

      递归函数在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函 数。(1) 递归就是在过程或函数里调用自身。(2) 在使...

38170
来自专栏静晴轩

Javascript数组操作

使用JS也算有段时日,然对于数组的使用,总局限于很初级水平,且每每使用总要查下API,或者写个小Demo测试下才算放心,一来二去,浪费不少时间;思虑下,堪能如此...

73480
来自专栏desperate633

LintCode 最长上升子序列题目分析代码

说明 最长上升子序列的定义: 最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列,这种子序列不一定是连续的或者唯一的。http...

9220
来自专栏锦小年的博客

python学习笔记3.3-高级函数技巧

在使用函数的时候,如果能合理的使用一些技巧,对于代码的阅读性以及程序的结构都是很有帮助的。常用的技巧有递归函数、高阶函数等。 1 递归函数 递归函数的定义就是在...

19690
来自专栏大数据学习笔记

Spark2.x学习笔记:2、Scala简单例子

2、 Scala简单例子 参考教程:https://yq.aliyun.com/topic/69 2.1 交互式编程 spark-shell是Spark交互式...

57180

扫码关注云+社区

领取腾讯云代金券