前言

代码随想录算法训练营day57

一、Leetcode 647. 回文子串

1.题目

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

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

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

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

示例 1：

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

示例 2：

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

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/palindromic-substrings

2.解题思路

方法一：中心拓展

思路与算法

计算有多少个回文子串的最朴素方法就是枚举出所有的回文子串，而枚举出所有的回文字串又有两种思路，分别是：

1. 枚举出所有的子串，然后再判断这些子串是否是回文；
2. 枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展。

假设字符串的长度为 nn。我们可以看出前者会用 O(n2)O(n2) 的时间枚举出所有的子串 s[li⋯ri]s[li⋯ri]，然后再用 O(ri−li+1)O(ri−li+1) 的时间检测当前的子串是否是回文，整个算法的时间复杂度是 O(n3)O(n3)。而后者枚举回文中心的是 O(n)O(n) 的，对于每个回文中心拓展的次数也是 O(n)O(n) 的，所以时间复杂度是 O(n2)O(n2)。所以我们选择第二种方法来枚举所有的回文子串。

在实现的时候，我们需要处理一个问题，即如何有序地枚举所有可能的回文中心，我们需要考虑回文长度是奇数和回文长度是偶数的两种情况。如果回文长度是奇数，那么回文中心是一个字符；如果回文长度是偶数，那么中心是两个字符。当然你可以做两次循环来分别枚举奇数长度和偶数长度的回文，但是我们也可以用一个循环搞定。我们不妨写一组出来观察观察，假设 n=4n=4，我们可以把可能的回文中心列出来： 编号 ii 回文中心左起始位置 lili 回文中心右起始位置 riri 0 0 0 1 0 1 2 1 1 3 1 2 4 2 2 5 2 3 6 3 3

由此我们可以看出长度为 nn 的字符串会生成 2n−12n−1 组回文中心 [li,ri][li,ri]，其中 li=⌊i2⌋li=⌊2i⌋，ri=li+(i mod 2)ri=li+(imod2)。这样我们只要从 00 到 2n−22n−2 遍历 ii，就可以得到所有可能的回文中心，这样就把奇数长度和偶数长度两种情况统一起来了。

3.代码实现

```java class Solution { public int countSubstrings(String s) { int n = s.length(), ans = 0; for (int i = 0; i < 2 * n - 1; ++i) { int l = i / 2, r = i / 2 + i % 2; while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) { --l; ++r; ++ans; } } return ans; } }
```

二、Leetcode 516.最长回文子序列

1.题目

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

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

示例 1：

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

示例 2：

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

提示：

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

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/longest-palindromic-subsequence

2.解题思路

方法一：动态规划

对于一个子序列而言，如果它是回文子序列，并且长度大于 22，那么将它首尾的两个字符去除之后，它仍然是个回文子序列。因此可以用动态规划的方法计算给定字符串的最长回文子序列。

用 dp[i][j]dp[i][j] 表示字符串 ss 的下标范围 [i,j][i,j] 内的最长回文子序列的长度。假设字符串 ss 的长度为 nn，则只有当 0≤i≤j

由于任何长度为 11 的子序列都是回文子序列，因此动态规划的边界情况是，对任意 0≤i

当 i

1. 如果 s[i]=s[j]s[i]=s[j]，则首先得到 ss 的下标范围 [i+1,j−1][i+1,j−1] 内的最长回文子序列，然后在该子序列的首尾分别添加 s[i]s[i] 和 s[j]s[j]，即可得到 ss 的下标范围 [i,j][i,j] 内的最长回文子序列，因此 dp[i][j]=dp[i+1][j−1]+2dp[i][j]=dp[i+1][j−1]+2；
2. 
3. 如果 s[i]≠s[j]s[i]=s[j]，则 s[i]s[i] 和 s[j]s[j] 不可能同时作为同一个回文子序列的首尾，因此 dp[i][j]=max⁡(dp[i+1][j],dp[i][j−1])dp[i][j]=max(dp[i+1][j],dp[i][j−1])。

由于状态转移方程都是从长度较短的子序列向长度较长的子序列转移，因此需要注意动态规划的循环顺序。

最终得到 dp[0][n−1]dp[0][n−1] 即为字符串 ss 的最长回文子序列的长度。

3.代码实现

```java class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); int[][] dp = new int[n][n]; for (int i = n - 1; i >= 0; i--) { dp[i][i] = 1; char c1 = s.charAt(i); for (int j = i + 1; j < n; j++) { char c2 = s.charAt(j); if (c1 == c2) { 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][n - 1]; } }
```