leetcode上两个字符串之间的动态规划类题目

1 总结

1.1 为什么转移数组是二维而不是一维？

一般我们都知道给定一个字符串s，当我们固定以当前索引i为子串的结尾时，则这种固定方法一共有n种，假设我们称这N个子串为结尾子串；

一般字符串之间的动态规划涉及到两个字符串，且涉及到S的结尾子串和T结尾子串的转换问题，那么两个字符串的所有结尾子串一共有n^2级别的转换组合，且长度更大的结尾子串之间的转换一般会利用到短串之间的转换数值。所以这个时候我们定义的dp的长度是二维的而不是一维

1.2 dp[i][j]有哪几种表达意思？

1 我在1.1中提到的这种，结尾子串i（S中以i结尾的子串）和结尾子串j，比如LC1143. 最长公共子序列， LC72. 编辑距离，LC97. 交错字符串
2 表示一个字符串中的子串区间，经典题目和回文串相关，比如 LC5. 最长回文子串， 这是字节常考题目

2 两个字符串之间的dp

2.1 LC1143. 最长公共子序列

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    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][n];
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-common-subsequence/solutions/696763/zui-chang-gong-gong-zi-xu-lie-by-leetcod-y7u0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.2 LC72. 编辑距离

class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        // 第一行
        for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j - 1] + 1;
        // 第一列
        for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
            }
        }
        return dp[n1][n2];  
    }
}

作者：powcai
链接：https://leetcode.cn/problems/edit-distance/solutions/6455/zi-di-xiang-shang-he-zi-ding-xiang-xia-by-powcai-3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.3 LC97. 交错字符串

    public boolean isInterleave3(String s1, String s2, String s3) {
        
        int n1=s1.length();
        int n2=s2.length();
        int n3=s3.length();

        if(n1+n2!=n3){
            return false;
        }
        // 1）如果来自s1[i-1]，则dp[i][j] 为：s1前缀长度i-1 + s2前缀长度j 能否交错组成s3前缀长度i+j-1，即：dp[i-1][j]
        // 2）如果来自s2[j-1]，则dp[i][j] 为：s1前缀长度i + s2前缀长度j-1 能否交错组成s3前缀长度i+j-1，即：dp[i][j-1]

        // dp[i][j] = (s1[i-1] == s3[i+j-1] && dp[i-1][j]) || 
        //            (s2[j-1] == s3[i+j-1] && dp[i][j-1]);
        boolean[][]f=new boolean[n1+1][n2+1];   
        f[0][0]=true;
        for(int i=0;i<=n1;i++){
            for(int j=0;j<=n2;j++){
                int p=i+j-1;
                if(i>0){
                    f[i][j]=f[i][j]||(f[i-1][j]&&s1.charAt(i-1)==s3.charAt(p));
                }
                if(j>0){
                    f[i][j]=f[i][j]||(f[i][j-1]&&s2.charAt(j-1)==s3.charAt(p));

                }
            }
        }
        return f[n1][n2];
    }
    

3 回文串dp

3.1 LC5. 最长回文子串

public class Solution {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }

                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-palindromic-substring/solutions/255195/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。