喝牛奶的牛

2020-11-29 03:15 已编辑中国银联_科技事业部_应用开发

关注

字符串(力扣)

0. 模版技巧总结

DP数组边界条件

在很多的题目中，动态数组依赖上边和左边的数，dp[i][j] = dp[i-1][j]+dp[i][j-1]，这就使得我们不得不处理复杂的边界情况，单独的为第一行和第一列，乃至dp[0][0]去计算数值，非常麻烦！

比如在最长公共子序列问题中，要单独处理边界，原因就是后续的传递公式中dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]+1);，必须要考虑i和j要大于0。

int[][] dp = new int[M][N];
dp[0][0] = str1.charAt(0) == str2.charAt(0) ? 1 : 0;
// 第一列
for (int i = 1; i < M; ++i){
    dp[i][0] = Math.max(dp[i-1][0], str1.charAt(i) == str2.charAt(0) ? 1 : 0);
}

// 第一行
for (int j = 1; j < N; ++j){
    dp[0][j] = Math.max(dp[0][j-1], str1.charAt(0) == str2.charAt(j) ? 1 : 0);
}

一个巧妙的技巧就是初始化DP数组时多增加一层。这样第一行和第一列默认就是0，通常实际情况也是0，比如最长公共子序列问题中，多增加一层后，第一行和第一列就被看作是空字符和空字符的公共子序列。

// 设置dp数组，多增加一层
int M = str1.length()+1;
int N = str2.length()+1;
int[][] dp = new int[M][N];

// 直接计算
for (int i = 1; i < str1.length()+1; i++){
    for (int j = 1; j < str2.length()+1; j++){
        if (str1.charAt(i-1) == str2.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[M-1][N-1];

为什么多增加一层就是对的呢？因为我们从第二行，列开始处理，就避免了之前i，j必须大于0的问题。而且我们仔细分析之前两种方法，其中前一种中，单独处理第一行列的方式其实就是和后续大循环中的思想是一样的，只是一种特殊边界的妥协！所以这类题目都可以用这种方法来避免处理边界。
比如：最长公共子序列，最长公共子串

但是有一些方法不能使用这个技巧，因为它们的边界处理和大循环中的不一致！
比如：UniquePath（机器人路径）问题中，边界条件就要单独处理。
UPI中第一行和第一列都是1，因为只能有一种走法。
UPII中第一行和第一列，一旦遇到障碍物后，后续的点都不可到达都为0。

1. 经典DP

最长升序子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。经典单子串问题

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

解题思路:
解题思路的动画可以参考liweiwei1419

方法一：

动态规划的思想，设置一个dp数组，它表示，dp[i]是以arr[i]结尾的最长升序子序列的长度。很自然的dp[0]就初始化为1，因为一个数也是长度为一的升序子序列。如何求dp[i]就是，在arr[0~i-1]中遍历所有的数，如果有arr[j]小于arr[i]，其中j～[0,i-1]，那么它对应dp[j]就可以和arr[i]组成一个新的升序子序列且长度是dp[j]+1，求里面最长的那个就是dp[i]。

图片说明

最后我们会得到一个和arr长度一样的dp数组，它是每个以arr[i]结尾的最长升序子序列的长度，我们期望的是这个dp数组的最大值，而不是最后一个值！我们要返回一个int数不是数组。

算法复杂度，时间：O(Nˆ2), 空间O(N)

public static int lengthOfLIS(int[] nums) {
    // 边界情况
    if(nums == null || nums.length == 0){
        return 0;
    }
    // 设置dp数组，含义是: dp[i]，以arr[i]结尾的最长升序子序列的长度
    // dp[i] 初始值为1
    // dp[i] = Max{ arr[从0到(i-1)中]所有比arr[i]小的dp[j]+1 }
    int len = nums.length;
    int[] dp = new int[len];
    int max = 0;
    for (int i=0; i<len; i++){
        // 初始值为1，就算你是最大的，你的LIS也至少是1
        dp[i] = 1;
        for (int j=0; j<i; j++){
            if (nums[j] < nums[i]){
                dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

方法二：
贪心和二分查找的思想，重新定义目标值，构造一个辅助数组tails，tails[i] 表示长度为i+1的LIS最小结尾数，tails的有效范围从0-0开始。基于贪心的思想，如果已经得到的上升子序列的结尾的数越小，遍历的时候后面接上一个数，就会有更大的可能性构成一个更长的上升子序列。

更新tails数组的思想是，end是tails的左边界限，从0开始。

遍历nums数组，若nums[i]检查到，ends有效区中没有比它大的数，则有效区加1，tails[end+1]=nums[i]
若nums[i]不是ends有效区中最大的，那么在tails数组中找到>=它最左的位置[不妨设为k]，替换掉它，它就是新的长度为k+1的LIS最小结尾数，结合下面的例子更好理解，上面的链接中还有动图。

这个方法能把时间复杂度降到O(NlogN)，这非常的重要，有个笔试题就是只能这个复杂度才能通过！它快的原因就是在查找排序数组中>=x的最左位置时，采用了模版的二分查找。细细评味，这个查找>=它最左的位置，就是找到第一个比他大的数，快速的替换他，满足贪心策略。

给定数组[10, 9, 2, 5, 3, 7, 101, 18]，开始遍历数组，

初始化tails数组tails[0]=10，这表示长度为1的LIS最小结尾数是10
接下来遇到了9，它的插入位置就是0，把10替换掉，这表示长度为1的LIS最小结尾数是9
同理，遇到2时就有tails[0]=2
遇到5时，比tails中都大，则end有效区+1，tails[1]=5,这表示长度为2的LIS最小结尾数是5
遇到3，把5更新了，tails[1]=3
遇到7，比tails中都大，则end有效区+1，tails[2]=7,这表示长度为3的LIS最小结尾数是7
同理101，tails[3]=101
最后是18，把101更新了，tails[3]=18
最后返回end有效区+1，就是最长的长度

public static int getDpWithBinarySearch(int[] nums){
    // 利用贪心，二分法 和 辅助数组让时间复杂度降低到 O(NlogN)
    // 辅助数组 tails, tails[i] 表示长度为i+1的LIS最小结尾数，tails的有效范围从0-0开始
    // end是tails的左边界限
    // 若nums[i]检查到，ends有效区中没有比它大的数，则有效区加1，tails[end+1]=nums[i]
    // 遍历完所有的nums后，end+1就是LIS的长度

    // 二分法的三个变量
    int l = 0;
    int r = 0;
    int m = 0;
    // dp数组
    int[] dp = new int[nums.length];
    // 存放最小结尾数的数组，暂时有效区是0-0
    int[] tails = new int[nums.length];
    // 表示有效区右边界
    int end = 0;
    dp[0] = 1;
    tails[0] = nums[0];
    for (int i=1; i<nums.length; i++){
        if (nums[i] > tails[end]){
            // 有效区加一
            end++;
            tails[end] = nums[i];
        }else {
            // 二分找到在ends中最左边的 >= nums[i]的位置
            // 也就是在为nums[i]找插入替代的位置！
            l = 0;
            r = end;
            while(l<= r){
                m = l + ((r - l) >> 1);
                if (tails[m] >= nums[i]){
                    r = m - 1;
                }else{
                    l = m + 1;
                }
            }
            // 最后返回的是 l or r+1 就是<=nums[i] 最左边的位置也就是插入位置
            tails[l] = nums[i];
        }
        dp[i] = end + 1;
    }
    end++;
    //也可以return end;
    return dp[dp.length-1];
}

最长公共子序列

LC Nr. 1143
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

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

解题思路:
dp[i][j]的含义是str1[0..i]与str2[0..j]的最长公共子序列的长度。矩阵dp第一列即dp[0..M-1][0]，dp[i][0]的含义是str1[0..i]与str2[0]的最长公共子序列长度。

str2[0]只有一个字符，所以dp[i][0]最大为1。如果str1[i]==str2[0]，令dp[i][0]=1，一旦dp[i][0]被设置为1，之后的dp[i+1..M-1][0]也都为1。

dp[i][j]的只来自于三种可能。

可能是dp[i-1][j]，代表str1[0..i-1]与str2[0..j]的最长公共子序列长度。
可能是dp[i][j-1]，代表str1[0..i]与str2[0..j-1]的最长公共子序列长度。
如果str1[i]==str2[j]，还可能是dp[i-1][j-1]+1。这个如果成立是最大的

// 得到dp数组
public static int[][] getDP(String str1, String str2){
    if (str1==null || str2==null || str1=="" || str2==""){
        return null;
    }
    // 通过dp数组得到最长的长度
    int M = str1.length();
    int N = str2.length();

    int[][] dp = new int[M][N];
    dp[0][0] = str1.charAt(0) == str2.charAt(0) ? 1 : 0;
    // 第一列
    for (int i = 1; i < M; ++i){
        dp[i][0] = Math.max(dp[i-1][0], str1.charAt(i) == str2.charAt(0) ? 1 : 0);
    }

    // 第一行
    for (int j = 1; j < N; ++j){
        dp[0][j] = Math.max(dp[0][j-1], str1.charAt(0) == str2.charAt(j) ? 1 : 0);
    }

    // 普通位置: 三种可能性
    for (int i=1; i<M; ++i){
        for (int j=1; j<N; ++j){
            dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            if (str1.charAt(i) == str2.charAt(j)){
                dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]+1);
            }
        }
    }
    return dp;
}

上面方法得到的是DP数组，最后结果在DP数组的最右下角。但是上面的方法要单独的处理第一行和第一列很繁琐，根据之前介绍的技巧，分析可知，第一行列的逻辑和大循环其实都一致，只是妥协了边界。下面的方法，新增加一行列，这代表空字符，结果都是0。图片来自labuladong

图片说明

方法二：技巧行增加一行列

public static int getDP2(String str1, String str2){
    // 参考力扣上的东哥的做法，不用特别计算第一列和第一层的数，但是dp数组的尺寸要加1
    if (str1==null || str2==null || str1.length()==0 || str2.length()==0){
        return 0;
    }

    // 设置dp数组
    int M = str1.length()+1;
    int N = str2.length()+1;
    int[][] dp = new int[M][N];

    // 直接计算
    for (int i = 1; i < str1.length()+1; i++){
        for (int j = 1; j < str2.length()+1; j++){
            if (str1.charAt(i-1) == str2.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[M-1][N-1];
}

方法二改进：空间压缩

DP[i][j]的取值，与上方，左方，和斜上面有关，因此可以用滚动数组，只计算上下数组的相对数量关系就可以递推出答案。

图片说明

public static int getDP3(String str1, String str2){
    // 参考力扣上的东哥的做法，不用特别计算第一列和第一层的数，但是dp数组的尺寸要加1
    // 在getDP2的基础上 空间压缩 力扣上性能提升！
    if (str1==null || str2==null || str1.length()==0 || str2.length()==0){
        return 0;
    }

    // 设置dp数组
    int M = str1.length()+1;
    int N = str2.length()+1;
    int[] pre = new int[N];
    int[] cur = new int[N];

    // 直接计算
    for (int i = 1; i < M; i++){
        for (int j = 1; j < N; j++){
            if (str1.charAt(i-1) == str2.charAt(j-1)){
                cur[j] = pre[j-1] + 1;
            }else {
                cur[j] = Math.max(pre[j], cur[j-1]);
            }
        }
        pre = cur.clone();
    }
    return cur[N-1];
}

最长公共子串的长度

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

示例1:
str1="1AB2345CD"，str2="12345EF"，返回"2345"。

解题思路:
参考我敬爱的左程云老师的“程序员代码面试指南：最优解第二版”。
最核心的思想就是，dp[i][j]的含义是，在必须把str1[i]和str2[j]当作公共子串最后一个字符的情况下，公共子串最长能有多长。它不像上一题子序列有更广义的连续性，子串更加严格。

比如str1="A1234B"，str2="CD1234"，dp[3][4]的含义是在必须把str1[3](即'3')和str2[4](即'3')当作公共子串最后一个字符的情况下，公共子串最长能有多长。这种情况下的最长公共子串为"123"，所以dp[3][4]为3。

比如str1="A12E4B"，str2="CD12F4"，dp[3][4]的含义是在必须把str1[3](即'E')和str2[4](即'F')当作公共子串最后一个字符的情况下，公共子串最长能有多长。这种情况下根本不能构成公共子串，所以dp[3][4]为0。

public static int getLengthOfLCStr(String text1, String text2){
    // dp[i][j]的含义是:
    // 在必须把str1[i]和str2[j]当作公共子串最后一个字符的情况下，公共子串最长能有多长。
    if (text1==null || text2==null || text1=="" || text2==""){
        return 0;
    }

    int M = text1.length();
    int N = text2.length();
    int[][] dp = new int[M][N];

    // 第一列的初始化
    for(int i=0; i<M; i++){
        if (text1.charAt(i) == text2.charAt(0)){
            dp[i][0] = 1;
        }
    }
    // 第一行的初始化
    for (int j=0; j<N; j++){
        if (text1.charAt(0) == text2.charAt(j)){
            dp[0][j] = 1;
        }
    }

    int max = 0;
    // 从左向右 从上向下计算
    for (int i=1; i<M; i++){
        for (int j=1; j<N; j++){
            if (text1.charAt(i) == text2.charAt(j)){
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            max = Math.max(max, dp[i][j]);
        }
    }
    return max;
}

方法二：技巧性的增加一行列

观察分析第一种方法，DP数组的递推就是根据对角线元素，所以额外的增加一行一列，它的物理含义就是“空字符串”，值都是0，这样后续的从第一个字符算起的时候，就可以直接计算不用处理边界情况了。

public static int getLCStrLength(String str1, String str2){
    if (str1 == null || str1 == "" || str2 == null || str2 == ""){
        return 0;
    }

    int rows = str1.length()+1;
    int cols = str2.length()+1;
    int[][] dp = new int[rows][cols];
    int len = 0;
    for (int i = 1; i < rows; i++){
        for (int j = 1; j < cols; j++){
            if(str1.charAt(i-1) == str2.charAt(j-1)){
                dp[i][j] = dp[i-1][j-1] + 1;
                len = Math.max(len, dp[i][j]);
            }
        }
    }
    return len;
}

方法二改进：空间压缩的思路是基于矩形对角线，计算比较复杂。

我们注意到计算每一个dp[i][j]的时候，最多只需要其左上方dp[i-1][j-1]的值，所以按照斜线方向来计算所有的值，只需要一个变量就可以计算出所有位置的值。

每一条斜线在计算之前生成整型变量len，len表示左上方位置的值，初始时len=0。从斜线最左上的位置开始向右下方依次计算每个位置的值，假设计算到位置(i，j)，此时len表示位置(i-1，j-1)的值。如果str1[i]==str2[j]，那么位置(i，j)的值为len+1，如果str1[i]! =str2[j]，那么位置(i，j)的值为0。计算后将len更新成位置(i，j)的值，然后计算下一个位置，即(i+1，j+1)位置的值。依次计算下去就可以得到斜线上每个位置的值，然后算下一条斜线。用全局变量max记录所有位置的值中的最大值。此处引用左老师的书，非常好一定要买来看看！

图片说明

对角线遍历方法的循环方式非常奇特，首先是行变量row控制最大的循环，从0开始，
内层循环中，先控制对角线方向递增，就是(i,j)在不越界的情况下变成(i+1, j+1)。当越界后，就是外层循环的递增条件，每次都是col减一，直到col等于0时换成每次row加一，直到row>=行数, 循环结束。

public static String getLCStrWithSpaceCompress(String str1, String str2){

    if (str1==null || str2==null || str1=="" || str2==""){
        return null;
    }
    // str1是较短的字符串 str2是最长的字符串
    int rows = 0;
    int cols = str2.length()-1;

    // 记录子串长度的最大值
    int max = 0;
    // 最长子串的最后下标
    int end = 0;

    // 从最右上角开始，先是rows=0，cols递减，当cols=0后，rows递增，最后推出循环
    while(rows < str1.length()){
        int i = rows;
        int j = cols;
        // 长度临时变量, 记录每条对角线的情况
        int len = 0;
        // 控制一条斜线遍历
        while (i<str1.length() && j<str2.length()){
            if (str1.charAt(i)!=str2.charAt(j)){
                len = 0;
            }else{
                len++;
            }
            // 寻找最大值
            if (len > max){
                max = len;
                end = i;
            }
            ++i;
            ++j;
        }
        // 遍历完一条对角线了
        if (cols > 0){
            cols--;
        }else {
            rows++;
        }
    }
    return str1.substring(end-max+1, end+1);
}

最长公共子串输出

给定两个字符串str1和str2，返回两个字符串的最长公共子串, 输出较短字符串中先出现的那个。

解题思路:

根据之前的分析, 采用动态规划的思路计算的DP[i][j]，表示以str1[i],str[j]结尾的公共子串的长度, 当某个DP[i][j]最大时，其i就表示最长公共子串在str1中结尾的下标，再计算出长度，就可以在str1中还原出最长子串且保证是第一个，因此str1是较短的字符串，str2较长的。

此外要注意的是在利用技巧增加一行一列后，要注意i,j的含义。还有java的库函数str1.substring(startIndex, endIndex), 是获取子串从startIndex开始，到endIndex结束。。

public static String getLCStr(String text1, String text2){
    // 优先从较短字符串中返回 最长公共子串
    if (text1==null || text2==null || text1=="" || text2==""){
        return null;
    }

    int rows = text1.length();
    int cols = text2.length();
    // 多加一行就不用判断特殊情况了
    int[][] dp = new int[rows+1][cols+1];
    // 记录最长子串的长度和结束下标
    int max = 0;
    int end = 0;

    // 要注意这里 i,j 的含义
    // dp[i][j] 是 text1中第i字符 对 text2中j字符
    for (int i=0; i<rows; i++){
        for (int j=0; j<cols; j++){
            if (text1.charAt(i) == text2.charAt(j)){
                dp[i+1][j+1] = dp[i][j] + 1;
            }
            if (dp[i+1][j+1] > max){
                max = dp[i+1][j+1];
                end = i;
            }
        }
    }


    // 要注意这里 i,j 的含义
    // dp[i][j] 是 text1中第i+1字符 对 text2中j+1字符
    for (int i=1; i<=rows; i++){
        for (int j=1; j<=cols; j++){
            if (text1.charAt(i-1) == text2.charAt(j-1)){
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            if (dp[i][j] > max){
                max = dp[i][j];
                end = i-1;
            }
        }
    }
    // 子串从end开始计算，一共max长度，所以起始字符是 str[end-max+1]
    // end+1是结束下表，是左闭右开区间，所以实际取str[end]，和函数性质有关是exclusive
    return text1.substring(end-max+1, end+1);
}

2. 线性DP

3. 匹配DP

编辑距离

LC72

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
插入一个字符，代价为insertCost-ic
删除一个字符，代价为deleteCost-dc
替换一个字符，代价为replaceCost-rc

解题思路：
参考左老师的算法书，程序员代码面试指南:IT名企算法与数据结构题目最优解
关键在于DP数组的定义，DP[i][j]表示把字符串str1[0...i-1]编辑成str2[0...j-1]的最小代价，如果每种操作的代价都是1，也就是最小操作数。

dp[0][0]=0，表示str1空的子串编辑成str2空的子串的代价为0。
矩阵dp第一列即dp[0..M-1][0]。dp[i][0]表示str1[0..i-1]编辑成空串的最小代价，毫无疑问，是把str1[0..i-1]所有的字符删掉的代价，所以dp[i][0]=dc*i。
矩阵dp第一行即dp[0][0..N-1]。dp[0][j]表示空串编辑成str2[0..j-1]的最小代价，毫无疑问，是在空串里插入str2[0..j-1]所有字符的代价，所以dp[0][j]=ic*j。

图片说明

其他位置按照从左到右，再从上到下来计算，dp[i][j]的值只可能来自以下四种情况。

当str1[i-1]==str2[j-1]时，由于遍历到了i和j，先把str1[0~i-2]编辑成str2[0~j-2]，其编辑代价是dp[i-1][j-1]，由于当前两个结尾字符相同，因此无需做任何操作即可得到，dp[i][j]=dp[i-1][j-1]。

当str1[i]!=str2[j]时，可以进行的操作有3个:

① 替换操作:
先把str1[0~i-2]编辑成str2[0~j-2]，由于只是当前位置的字符不匹配，进行替换操作后两者变得相同，所以此时dp[i][j] = dp[i-1][j-1]+ rc

② 删除操作:
如果把str1[0~i-2]编辑成str2[0~j-1]，此时多出了str1[i-1]位置的一个字符，应把它删除掉，才能使此时str1和str2整体匹配，因此此时dp[i][j] = dp[i-1][j] + dc

③ 插入操作:
如果把str1[0~i-1]编辑成str2[0~j-2]，但是str1长度不够，此时只需要在str[i-1]后面插入一个与str2[j-1]相同的字符，使得编辑后的str1和str2能匹配上，且长度一样了，所以此时dp[i][j] = dp[i][j-1] + ic

由于题目所要求的是要最少的操作数，所以需要在这三个操作中选取一个最小的值赋格当前的dp[i][j]。代码如下：

/*
 * min edit cost
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @param ic int整型 insert cost
 * @param dc int整型 delete cost
 * @param rc int整型 replace cost
 * @return int整型
 */
public static int minEditCost (String str1, String str2, int ic, int dc, int rc) {
    // write code here
    // word1为空，编辑word2.length()次的插入
    if (str1.length() == 0) return str2.length() * ic;
    // word2为空，编辑word1.length()次的删除
    if (str2.length() == 0) return str1.length() * dc;
    int rows = str1.length() + 1;
    int cols = str2.length() + 1;
    int[][] dp = new int[rows][cols];

    // 第一行表示: "" 编辑成 word2[0~j-1]，都是插入操作
    for (int j = 1; j < cols; j++){
        dp[0][j] = j * ic;
    }

    // 第一列表示: word1[0~i-1] 编辑成 ""，都是删除操作
    for (int i = 1; i < rows; i++){
        dp[i][0] = i * dc;
    }

    for (int i = 1; i < rows; i++){
        for (int j = 1; j < cols; j++){
            if (str1.charAt(i-1) == str2.charAt(j-1)){
                dp[i][j] = dp[i-1][j-1];
                continue;
            }else { // 替换操作
                dp[i][j] = dp[i-1][j-1] + rc;
            }
            // 删除
            dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + dc);
            // 插入
            dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + ic);
        }
    }
    return dp[rows-1][cols-1];
}

空间压缩技巧，不是这个题目的重点。以前的空间压缩都是上方和左方的点，可以通过滚动数组解决，在这个题目中还有额外的左上角的点，所以需要一个额外的变量，并且主要空间压缩时，要选取要选择循环的方向，让短序列作为完成序列，长序列作为目标序列，让目标序列编辑成完成序列，这样只需要短序列长度的数组的额外空间，并遍历长序列长度的次数。

这里展示的是每个修改都是等代价的，如果不是的话，在交换长短序列时，如果目标序列发生改变，要注意把插入代价ic和删除代价dc交换一下即可。

public static int minDistanceWithSpaceCompress (String word1, String word2) {
    // 洗数据，有空字符串的情况
    if (word1.length()==0){
        // 执行word2长度的插入操作
        return word2.length();
    }
    if (word2.length()==0){
        // 执行word1长度的删除操作
        return word1.length();
    }

    // 空间压缩，要选择循环的方向，让短序列作为完成序列，长序列作为目标序列，让目标序列变成完成序列
    // 这样只需要短序列长度的数组，并遍历长序列长度的次数
    char[] ch1 = word1.toCharArray();
    char[] ch2 = word2.toCharArray();
    char[] longWord = ch1.length >= ch2.length ? ch1 : ch2;
    char[] shortWord = ch1.length < ch2.length ? ch1 : ch2;
    int[] dp = new int[shortWord.length + 1];

    // 初始化：短序列的第一次遍历，是针对str1是空序列
    for (int i = 1; i < dp.length; i++){
        // i * insertCost: 空序列变成str2[1....end]
        dp[i] = i;
    }

    // 以往的空间压缩都是，依赖与上方和左方元素，这次多了一个左上方，需要额外一个变量记录
    for (int i = 1; i <= longWord.length; i++){
        // 临时变量记录左上角的值
        int corner = dp[0];
        // 竖直方向遍历的初始化：i*deleteCost
        dp[0] = i;
        for (int j = 1; j <= shortWord.length; j++){
            // 记录下dp[j]，也就是上方数据temp = dp[i-1][j]
            int temp = dp[j];
            if (longWord[i-1] == shortWord[j-1]){
                // corner = dp[i-1][j-1]
                dp[j] = corner;
                continue;
            }else {
                // 替换
                dp[j] = corner + 1;
            }
            // 插入操作: dp[j-1]->dp[i][j-1]
            // dp[i][j-1] + insertCost
            dp[j] = Math.min(dp[j], dp[j-1] + 1);
            // dp[i-1][j] + deleteCost
            dp[j] = Math.min(dp[j], temp + 1);
            corner = temp;
        }
    }
    return dp[shortWord.length];
}

4. 区间DP

5.其他问题

无重复字符的最长子串

Nr.3
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

解题思路:

利用哈希表记录每个出现的字符以其下标，当遇到重复的字符时，先判断重复的字符是否在left左指针的范围内，如果在，left更新到以前重复字符的下一个位置，如果不在，更新重复字符在哈希表中的下标记录，每次比较最大长度。

left就相当于统计“不重复子串长度的有效计算区”的边界，当在此区域内，新遍历的字符没有出现过(在哈希表里无记录)，则不重复子串的长度加1，如果出现了重复的字符(在哈希表里有记录)，有可能此记录是“上次left区里面”的旧字符，对于新left区来说是不重复的，因此要判断重复的记录与left的关系。

比如字符串:"abcddbcefga",当遍历到第二个d的时候，left此时在index=0的位置，查表可知被重复的d在index=3，因此left更新到index+1=4的位置，之前的长度到4，是目前最长的；
d在哈希表中更新到4，并开始继续遍历，长度并随之回归到1，之后遇到重复的'b','c','a'都会因为
没有大于left，而不会产生影响, 最终返回长度7(dcbcefga)。

代码:

public static int lengthOfLangestSubString( String str) {
if (str==null || str.length()==0){
    return 0;
}
// 左指针
int left = 0;
int maxLength = 0;
// 字母记录表
HashMap<Character, Integer> CharMap = new HashMap<>();
// 遍历字母
for(int i=0; i<str.length(); i++){
    // 如果有重复的字符，如果是在当前的有效区间内，则更新left
    // 比如: abcddbcdefga 最后一个a，是在哈希表中重复的，如果不设置left，并不判断它与left的范围，会错误的导致left更新到2
    if (CharMap.containsKey(str.charAt(i)) && CharMap.get(str.charAt(i)) >= left){
        left = CharMap.get(str.charAt(i)) + 1;
    }
    // 添加新的字符，更新他们的value
    CharMap.put(str.charAt(i), i);
    maxLength = Math.max(maxLength, i-left+1);
}