算法日记day 44（动归之编辑距离|回文字串|最长回文子序列）

本文主要是介绍算法日记day 44（动归之编辑距离|回文字串|最长回文子序列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、编辑距离

题目：

给你两个单词 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')

思路：

dp数组的含义是以i-1为结尾的字符串word1和以j-1长度为结尾的字符串word2所需要的步骤为dp[i][j]，有四种情况，如果本身两字符串所对应的元素相同，则不需要做任何操作，因此

dp[i][j] = dp[i-1][j-1]

如果需要对word1进行删除操作，相当于忽略掉word1中的第i-1位元素，这样的

dp[i][j] = dp[i-1][j] + 1

如果需要对word1进行添加操作，相当于对word2进行一次删除操作，例如word1="ab" word2="a"，可以删除word1中的b，或者添加word2中一位b，因此

dp[i][j] = dp[i][j-1] + 1

如果进行修改的操作，相当于字符串中其前i-2位和j-2位元素均相同，仅需改变其中i-1（j-1）位元素，因此

dp[i][j] = dp[i-1][j-1] + 1

对于需要操作的元素，应取三者中次数最少的值作为最终编辑距离

初始化操作，对于dp[i][0]，相当于长度为 i 的字符串word1转换为长度为0的字符串word2，仅需删除操作，次数为字符串word1的长度，因此

dp[i][0] = i

同理： dp[0][j] = j

代码：

public int minDistance(String word1, String word2) {// 初始化 dp 数组，dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作数int[][] dp = new int[word1.length() + 1][word2.length() + 1];// 设置 dp 数组的第一列，dp[i][0] 表示将 word1 的前 i 个字符转换为空字符串的操作数for (int i = 1; i <= word1.length(); i++)dp[i][0] = i;// 设置 dp 数组的第一行，dp[0][j] 表示将空字符串转换为 word2 的前 j 个字符的操作数for (int j = 1; j < word2.length() + 1; j++)dp[0][j] = j;// 填充 dp 数组for (int i = 1; i < word1.length() + 1; i++) {for (int j = 1; j <= word2.length(); j++) {// 如果当前字符相同，不需要增加额外的操作，继承前一个状态的值if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {// 如果字符不同，考虑三种操作：// 1. 替换字符：dp[i - 1][j - 1] + 1// 2. 删除字符：dp[i - 1][j] + 1// 3. 插入字符：dp[i][j - 1] + 1// 选择三者中的最小值作为当前状态的值dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;}}}// 返回将 word1 转换为 word2 所需的最小操作数return dp[word1.length()][word2.length()];
}

初始化 dp 数组：
- dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符的最小编辑距离。
第一列和第一行的初始化：
- dp[i][0] 表示将 word1 的前 i 个字符转换为空字符串的操作数，即删除操作的数量。
- dp[0][j] 表示将空字符串转换为 word2 的前 j 个字符的操作数，即插入操作的数量。
填充 dp 数组：
- 遍历所有可能的子问题，并根据当前字符是否相同来决定最小的操作数。
- 如果字符相同，继承前一个状态的值；如果字符不同，则选择替换、删除或插入操作中最小的代价。
返回结果：
- 最终的编辑距离是将 word1 的所有字符转换为 word2 的所有字符所需的最小操作数。

二、回文字串

题目：

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

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

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

示例 1：

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

示例 2：

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

思路：

首先定义一个boolean类型的dp数组，本题中dp数组的含义是在区间[i，j]的字符串中是回文字串的dp[i][j]为true

判断

由于回文串的特殊性，如果 i 与 j 的值相同，当 i 与 j 的距离满足 j - i <= 2时，都符合回文串的条件因此定义一个res收集结果，同时dp[i][j]为true，如果此时距离大于2，则需要比较dp[i+1][j-1]的值是否为true，如果是，则说明dp[i][j]是回文串，如果 i 与 j 的值不相同，则表示不是回文串

代码：

public int countSubstrings(String s) {// 将字符串转换为字符数组，方便使用索引访问字符char[] chars = s.toCharArray();int len = chars.length; // 获取字符数组的长度// 创建一个二维布尔数组 dp，dp[i][j] 表示子串 chars[i..j] 是否为回文boolean[][] dp = new boolean[len][len];int result = 0; // 结果变量，用于记录回文子串的总数量// 从字符串的末尾开始，逐步向前遍历所有可能的起始位置for (int i = len - 1; i >= 0; i--) {// 对于每个起始位置 i，遍历可能的结束位置 jfor (int j = i; j < len; j++) {// 检查当前子串 chars[i..j] 的首尾字符是否相同if (chars[i] == chars[j]) {// 当子串长度为 1 或 2 时，直接标记为回文子串// 1. 长度为 1 的子串（例如 "a"）// 2. 长度为 2 的子串（例如 "aa"）if (j - i <= 2) { // 子串长度小于或等于 2result++; // 增加回文子串计数dp[i][j] = true; // 标记 dp[i][j] 为回文} // 当子串长度大于 2 时，检查内部子串是否为回文// 3. 如果子串 chars[i+1..j-1] 为回文，则 chars[i..j] 也是回文else if (dp[i + 1][j - 1]) { result++; // 增加回文子串计数dp[i][j] = true; // 标记 dp[i][j] 为回文}}}}return result; // 返回总的回文子串数量
}

len 是字符串的长度。
dp 是一个二维布尔数组，dp[i][j] 用来记录子串 chars[i..j] 是否为回文。
result 用来累计回文子串的总数。
外层循环从字符串的末尾向前遍历起始位置 i。
内层循环从起始位置 i 遍历到字符串的末尾，考虑所有可能的结束位置 j。
首先，检查 chars[i] 是否等于 chars[j]。如果不相等，chars[i..j] 不能是回文子串。
对于长度为 1 或 2 的子串（即 j - i <= 2），直接判断为回文。
对于长度大于 2 的子串，需要检查内部子串 chars[i+1..j-1] 是否是回文。如果是，则 chars[i..j] 也是回文。
返回计算得到的回文子串总数。

三、最长回文子序列

题目：

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

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

示例 1：

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

示例 2：

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

思路：

首先dp数组的含义是在区间为[i，j]的字符串中最长回文子序列的长度为dp[i][j]

对于 i 与 j 相同的情况，若区间内是回文序列，则相对应的最长长度加2

dp[i][j] = dp[i+1][j-1] +2

如果 i 与 j 不相同，则取dp[i][j-1] 与dp[i-1][j] 中的最大值，即为

dp[i][j] = max(dp[i][j]，max(dp[i-1][j]，dp[i][j-1])

又dp[i][j] 依赖于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]

遍历顺序应为 i 从下往上，j 从左往右

代码：

public int longestPalindromeSubseq(String s) {int len = s.length(); // 获取字符串的长度// 创建一个二维数组 dp，其中 dp[i][j] 表示子串 s[i..j] 的最长回文子序列的长度int[][] dp = new int[len + 1][len + 1];// 初始化每个字符的最长回文子序列的长度为 1，因为任何单个字符都是回文的for (int i = 0; i < len; i++) {dp[i][i] = 1;}// 从字符串的倒数第二个字符开始，逐步向前遍历所有可能的起始位置for (int i = len - 1; i >= 0; i--) {// 对于每个起始位置 i，遍历可能的结束位置 jfor (int j = i + 1; j < len; j++) {// 如果子串 s[i..j] 的首尾字符相同if (s.charAt(i) == s.charAt(j)) {// 则子串 s[i..j] 的最长回文子序列长度为子串 s[i+1..j-1] 的长度 + 2dp[i][j] = dp[i + 1][j - 1] + 2;} else {// 如果首尾字符不同，则子串 s[i..j] 的最长回文子序列长度是// 子串 s[i+1..j] 和 s[i..j-1] 的最长回文子序列长度中的较大值dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);}}}// 返回整个字符串 s 的最长回文子序列的长度return dp[0][len - 1];
}

外层循环从字符串的倒数第二个字符向前遍历所有起始位置 i。
内层循环从起始位置 i 向后遍历可能的结束位置 j。
如果 s[i] 和 s[j] 相同，则子串 s[i..j] 的最长回文子序列长度等于 s[i+1..j-1] 的最长回文子序列长度加 2（包括 s[i] 和 s[j]）。
如果 s[i] 和 s[j] 不同，则子串 s[i..j] 的最长回文子序列长度是 s[i+1..j] 和 s[i..j-1] 中较大的值。