子串和子序列问题-动态规划向

 1. 子串子序列问题概述

        有关于子序列和子串的问题是字符串或者数组经常会遇到的问题，一般我们经常使用多指针，滑动窗口，回溯，动态规划的方式去解决，而本篇重点关注能用动态规划解决或者说明显使用动态规划解决的子串问题和子序列问题。

1.1 子串

        子串是字符串中的由连续字符组成的一个序列，重点在于连续。例如，"1AB2345CD"，那么"1AB23"，"5CD"都是相应的子串，而"12345CD"不是，已经不是连续的状态。

1.2 子序列

        字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串，那么很明显，子序列和子串最大的区别就是可以是不连续的。例如，"1AB2345CD"，"12345CD"就是它的一个子序列。

2. leetcode && nowcoder案例实战

1. NC127 最长公共子串

给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。 

输入：
"1AB2345CD","12345EF"
返回值：
"2345"

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        int[][] dp = new int[str1.length()][str2.length()];
        int max = 0;
        int index = 0;
        if(str1.charAt(0) == str2.charAt(0)) dp[0][0] = 1;
        for(int i = 1; i < str1.length(); i++){
            for(int j = 1; j < str2.length(); j++){
                if(str1.charAt(i) == str2.charAt(j)){
                    dp[i][j] = dp[i-1][j-1]+1;
                    if(dp[i][j] > max){
                        max = dp[i][j];
                        index = i-max+1;
                    }
                }
                else{
                    dp[i][j] = 0;
                }
            }
        }
        return str1.substring(index,index+max);
    }
}

分别想象成两个指针，分别重头到尾遍历，如下图所示。 

如果指针指向的内容相同，那么就是

如果不同

 

本体小结：（1）dp[i][j]表示字符串str1中第i个字符和str2种第j个字符为最后一个元素所构成的最长公共子串

                  （2）由于记录的是以i和j为结尾最大的，所以在比较过程中要是可保留最大值

2. leetcode647 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

class Solution {
    public int countSubstrings(String s) {
        if(s.length() < 2) return 1;
        boolean[][] dp = new boolean[s.length()][s.length()];
        int count = 0;
        for(int i = 0; i < s.length(); i++){
            for(int j = 0; j <= i; j++){
                if(s.charAt(i) == s.charAt(j)){
                    if(i - j < 2 || dp[i-1][j+1]){
                        dp[i][j] = true;
                        count++;
                    }
                }
            }
        } 
        return count;
    }
}

dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串；

当dp[i][j] = true 代表在（i,j）之间的子串是个回文串；

当dp[i][j] = false 代表在（i,j）之间的子串不是个回文串；

分为三种情况：（1）当s.charAt(i) != s.charAt(j) 那么把这个区间设置为false

                         （2）当s.charAt(i) == s.charAt(j) 那么需要考虑 i-1和j+1的位置的情况

                         （3）如果i和j的举例少于2证明子串是一个或者两个，就不需要考虑i-1和j+1了

本题小结：（1）把s.charAt(i) 和 s.charAt(j)之间的问题转换为i-1和j+1的问题

                  （2）注意特例i - j < 2的情况

3. leetcode5 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() < 2) return s;
        int maxlen = 1;
        int len = s.length();
        int index = 0;
        boolean[][] dp = new boolean[len][len];
        for(int i = 0; i < len; i++){
            for(int j = 0; j <=i; j++){
                if(s.charAt(i) == s.charAt(j)){
                    if(i- j < 2 || dp[i-1][j+1]){
                        dp[i][j] = true;
                        if(i-j+1 > maxlen){
                            maxlen = i-j+1;
                            index = j;
                        }
                    }
                }
            }
        }
        return s.substring(index,index+maxlen);
    }
}

和上题（leetcode647 回文子串） 相同 

dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串；

当dp[i][j] = true 代表在（i,j）之间的子串是个回文串；

当dp[i][j] = false 代表在（i,j）之间的子串不是个回文串；

本题小结：（1）本题就是需要保存一个长度的变量和其起始的位置，其他的思想和上题相同

4. leetcode1143 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。 

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length()+1][text2.length()+1];
        // if(text1.charAt(0) == text2.charAt(0)) dp[0][0] = 1;
        for(int i = 1; i <= text1.length(); i++){
            for(int j = 1; j <= text2.length(); j++){
                if(text1.charAt(i-1) == text2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

 dp[i][j] 表示 text1[0:i-1] 和 text2[0:j-1] 的最长公共子序列

“ 当 text1[i - 1] == text2[j - 1] 时，说明两个子字符串的最后一位相等，所以最长公共子序列又增加了 1，所以 dp[i][j] = dp[i - 1][j - 1] + 1；举个例子，比如对于 ac 和 bc 而言，他们的最长公共子序列的长度等于 a 和 b 的最长公共子序列长度 0 + 1 = 1。

当 text1[i - 1] != text2[j - 1] 时，说明两个子字符串的最后一位不相等，那么此时的状态 dp[i][j] 应该是 dp[i - 1][j] 和 dp[i][j - 1] 的最大值。举个例子，比如对于 ace 和 bc 而言，他们的最长公共子序列的长度等于 ① ace 和 b 的最长公共子序列长度0 与 ② ac 和 bc 的最长公共子序列长度1 的最大值，即 1。”   ----------【1】

当text1.charAt(i-1) == text2.charAt(j-1)

        

当text1.charAt(i-1) != text2.charAt(j-1)

        

本题小结：（1）不能先使用if(text1.charAt(0) == text2.charAt(0)) dp[0][0] = 1会漏掉状态

 5. leetcode300 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len =nums.length;
        int[] dp = new int[len+1];
        Arrays.fill(dp,1);
        int max = 1;
        for(int i = 0; i < len-1; i++){
            for(int j = i+1; j < len; j++){
                if(nums[j] > nums[i]) {
                    dp[j] =Math.max(dp[j],dp[i]+1);
                    max = Math.max(dp[j],max);
                }
            }
        }
        return max;
    }
}

dp[i] 表示：以 nums[i] 结尾 的「上升子序列」的长度

当猴一面一个数dp[j] > 前面一个数dp[i]时：

然后选取最大值：

黄色：已确定好数值区间得dp[i]，j为要求得dp值 

本题小结：（1）dp[i]代表以i为结尾的上升子序列，要在比较过程中保留最大值

 6. leetcode516 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
 

class Solution {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int[][] dp = new int[len][len];
        for(int i = len-1; i >= 0; i--){
            dp[i][i] = 1;
            for(int j = i+1; j < len; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1] + 2;
                }
                else{
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][len-1];
    }
}

dp[i][j] 代表从i到j的区间(左闭右闭)内最长的回文子序列的长度

那么，当s.charAt(i) == s.charAt(j)

当s.charAt(i) != s.charAt(j)

为何从尾到头遍历？

先看i在右边的情况：

那么很容易得到状态方程：

聪明的你已经发现了，当前状态是不能既由前方向和后方向一起得到的，动态规划的转移方程只能由已知的部分转移而来。

再看i在左边的情况：

到这里就熟悉了许多，经典三个角地推。 很容得出i要先知道i+1的信息，所以i从后往前推。

本题小结：（1）为何从尾到头遍历要注意以及dp[i][i] = 1要注意初始化

参考来源：（1）leetcode 负雪明烛 二维动态规划的常规套路

                  （2）牛客 数据结构和算法 动态规划解最长公共子串 

                  （3）leetcode jawhiow 两道回文子串的解法（详解中心扩展法） 文章来源地址https://uudwc.com/A/206oV