力扣练习题（2024/4/19）

1两个字符串的删除操作

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步可以删除任意一个字符串中的一个字符。

示例 1：

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例 2:

输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母

动态规划思路：

定义 dp[i][j] 为以第 i-1 个字符为结尾的字符串 word1，和以第 j-1 个字符为结尾的字符串 word2，想要达到相等，所需要删除元素的最少次数。
初始化 dp 数组：
- 当 word2 为空字符串时，word1 的任意子串都需要删除所有字符才能与之相等，因此 dp[i][0] = i。
- 当 word1 为空字符串时，无论 word2 如何，都不需要删除任何字符，因此 dp[0][j] = 0。这一步在代码中被默认初始化为 0。
状态转移方程：
- 当 word1[i - 1] == word2[j - 1]，即 word1 的第 i-1 个字符与 word2 的第 j-1 个字符相等时，不需要删除字符，dp[i][j] 可以由 dp[i - 1][j - 1] 继承而来。
- 当 word1[i - 1] != word2[j - 1]，即 word1 的第 i-1 个字符与 word2 的第 j-1 个字符不相等时，此时需要删除字符，dp[i][j] 可以由以下几种操作得到：
  1. 删除 word1 的第 i-1 个字符，转化为以 word1 的前 i-2 个字符与 word2 的前 j-1 个字符相等的状态，操作数加一，即 dp[i][j] = dp[i - 1][j] + 1。
  2. 删除 word2 的第 j-1 个字符，转化为以 word1 的前 i-1 个字符与 word2 的前 j-2 个字符相等的状态，操作数加一，即 dp[i][j] = dp[i][j - 1] + 1。
  3. 同时删除 word1 的第 i-1 个字符和 word2 的第 j-1 个字符，转化为以 word1 的前 i-2 个字符与 word2 的前 j-2 个字符相等的状态，操作数加二，即 dp[i][j] = dp[i - 1][j - 1] + 2。
最终返回 dp[word1.size()][word2.size()]，即以 word1 和 word2 为结尾的字符串相等所需要删除的最少次数。

代码：

class Solution {
public:
    int minDistance(string word1, string word2) {
        // 创建二维数组 dp，dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作数
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
        
        // 初始化 dp 数组：当 word2 为空字符串时，需要删除 word1 的所有字符；当 word1 为空字符串时，不需要删除任何字符
        for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
        for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
        
        // 动态规划计算最小操作数
        for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    // 当前字符相等，不需要额外操作，继承前一个状态的操作数
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 当前字符不相等，选择删除 word1 的第 i 个字符或者删除 word2 的第 j 个字符中操作数较小的情况
                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                }
            }
        }
        
        // 返回将 word1 转换为 word2 所需的最小操作数
        return dp[word1.size()][word2.size()];
    }
};

2 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

思路：

1. 定义 `dp[i][j]` 表示以下标 i-1 为结尾的字符串 `word1`，和以下标 j-1 为结尾的字符串 `word2`，最近编辑距离为 `dp[i][j]`。

2. 初始化二维数组 `dp`： - 初始化 `dp[i][0] = i`，表示当 `word2` 为空字符串时，将 `word1` 的前 `i` 个字符全部删除即可，操作次数为 `i`。 - 初始化 `dp[0][j] = j`，表示当 `word1` 为空字符串时，将 `word2` 的前 `j` 个字符全部插入即可，操作次数为 `j`。

3. 动态规划求解最小编辑距离： - 对于每个位置 `(i, j)`，如果 `word1[i - 1]` 等于 `word2[j - 1]`，说明当前字符相同，不需要进行操作，取左上角的值 `dp[i - 1][j - 1]`； - 如果当前字符不同，可以选择插入、删除、替换操作中的最小值，并加上一次操作： - `dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1`。

4. 最终返回 `dp[word1.size()][word2.size()]`，即将 `word1` 转换成 `word2` 所需的最小操作次数。这种动态规划的方法利用填表法，逐步计算出最小编辑距离，从而实现字符串之间的匹配和转换。

代码：

class Solution {
public:
    int minDistance(string word1, string word2) {
        // 创建二维数组 dp，dp[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小操作次数
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        
        // 初始化 dp 数组的第一行和第一列
        for(int i = 0; i <= word1.size(); i++) 
            dp[i][0] = i; // word2 为空字符串时，将 word1 的前 i 个字符全部删除即可
        for(int j = 0; j <= word2.size(); j++)  
            dp[0][j] = j; // word1 为空字符串时，将 word2 的前 j 个字符全部插入即可
        
        // 动态规划求解最小编辑距离
        for(int i = 1; i <= word1.size(); i++) {
            for(int j = 1; j <= word2.size(); j++) {
                if(word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1]; // 当前字符相同，不需要进行操作，取左上角的值
                } else {
                    // 当前字符不同，可以选择插入、删除、替换操作中的最小值，并加上一次操作
                    dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
                }
            }
        }
        
        // 返回最小编辑距离
        return dp[word1.size()][word2.size()];
    }
};

3回文子串

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

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

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

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

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

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

提示：

1 <= s.length <= 1000
s 由小写英文字母组成

思路：

首先，我们定义一个二维数组 dp，其中 dp[i][j] 表示字符串 s 中以索引 i 开始、索引 j 结束的子串是否为回文串。初始化时，我们将所有 dp[i][j] 的值设为 false，表示初始时所有子串都不是回文串。

然后，我们从字符串的末尾开始向前遍历，这样我们可以先计算出小区间的结果，再利用小区间的结果计算大区间的结果。对于每个索引 i，我们再从 i 开始向后遍历，对于每个索引 j，我们判断 s[i] 是否等于 s[j]：

如果 s[i] 等于 s[j]，则可能存在回文子串。我们进一步分析：
1. 如果 j - i 小于等于 1，说明子串长度为 1 或 2，此时 s[i] 和 s[j] 相等，所以子串是回文串，我们将结果加一，并将 dp[i][j] 设为 true。
2. 如果 j - i 大于 1，且 dp[i + 1][j - 1] 为 true，说明内部子串是回文串，且 s[i] 和 s[j] 相等，此时整个子串也是回文串，我们将结果加一，并将 dp[i][j] 设为 true。

最终，我们返回计算得到的回文子串的数量。

代码

class Solution {
public:
    int countSubstrings(string s) {
        // 创建二维数组 dp，dp[i][j] 表示 s 中以索引 i 开始、索引 j 结束的子串是否为回文串
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        
        // 从后向前遍历字符串 s，保证先计算出小区间的结果，再利用小区间的结果计算大区间的结果
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) { // 情况一：子串长度为 1 或 2
                        result++; // 单个字符或相邻字符构成的子串都是回文串
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 情况二：子串长度大于 2，且内部子串是回文串
                        result++; // 内部子串是回文串，且两端字符相同，则整个子串也是回文串
                        dp[i][j] = true;
                    }
                }
            }
        }
        
        // 返回回文子串的数量
        return result;
    }
};

4. 最长回文子序列

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

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

示例 1：

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

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

思路：

定义状态： 首先，我们需要定义动态规划状态。在这里，我们使用二维数组 dp[i][j]，其中 dp[i][j] 表示从字符串 s 的下标 i 到 j 之间的子串中的最长回文子序列长度。
状态转移方程： 接下来，我们需要找到状态之间的转移关系。当我们在考虑 dp[i][j] 时，我们可以根据 s[i] 和 s[j] 的关系来决定如何更新 dp[i][j] 的值：
- 如果 s[i] == s[j]，那么 dp[i][j] 可以由 dp[i + 1][j - 1] 推导而来，即 dp[i][j] = dp[i + 1][j - 1] + 2，因为两端相同的字符可以增加最长回文子序列的长度。
- 如果 s[i] != s[j]，那么 dp[i][j] 可以由 dp[i + 1][j] 和 dp[i][j - 1] 中的较大值推导而来，因为当前位置的字符不同，所以无法直接形成回文，只能取相邻子串中的最长回文子序列的长度作为当前子串的最长回文子序列长度，即 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])。
初始化： 我们需要对动态规划数组进行初始化。对角线上的元素 dp[i][i] 表示单个字符的子串为回文子序列，因此初始化为 1。
状态转移计算： 我们从字符串的末尾开始向前遍历，逐步计算出每个子串的最长回文子序列长度，直到计算出整个字符串的最长回文子序列长度。
返回结果： 最后，我们返回 dp[0][s.size() - 1]，即整个字符串的最长回文子序列长度

代码：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        // 创建二维数组 dp，dp[i][j] 表示以下标 i 到 j 之间的子串中的最长回文子序列长度
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        
        // 初始化 dp 数组的对角线，即单个字符的子串为回文子序列，长度为 1
        for (int i = 0; i < s.size(); i++) 
            dp[i][i] = 1;
        
        // 动态规划求解最长回文子序列长度
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2; // 当前字符相同，加上两端字符的最长回文子序列长度
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); // 当前字符不同，取相邻子串中的最长回文子序列长度
                }
            }
        }
        
        // 返回整个字符串的最长回文子序列长度
        return dp[0][s.size() - 1];
    }
};