代码随想录算法训练营第六十天 | LeetCode647 回文子串、LeetCode516 最长回文子序列

今日任务：

LeetCode647 回文子串
LeetCode516 最长回文子序列
动态规划总结

资料来源：

1 LeetCode647 回文子串

题目

给你一个字符串 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]为结尾的回文子序列的话，会发现它其实找不到递推关系，或者说它依赖于dp[i + 1][j + 1]和dp[i - 1][j - 1]就已经没法通过动规去求了，没法循环。

所以这类回文问题要通过dp数组求的是，对于dp[i][j]来说，它所储存的是从s[i]到s[j]这段连续字符串是否是回文串。它所依赖的就是dp[i + 1][j - 1]，也就是在从s[i + 1]到s[j - 1]这段连续字符串的基础上，再在首尾两个位置各加一个字符，这可比之前那个概念依赖要好循环多了。

递推过程上，先判断新加的字符是否相同，不相同直接就不是回文串了；如果相同，那么它是否是回文串就依赖于dp[i + 1][j - 1]了。另外还有两种情况：i==j，即字符串只有一个字符，那么它必定是回文串；j - i = 1，即字符串只有两个字符，那么如果s[i] == s[j]，它就是一个回文串了。记得过程中对是回文串的进行计数即可。

go
func countSubstrings(s string) int {
	dpArray := make([][]bool, len(s))
	for i := range dpArray {
		dpArray[i] = make([]bool, len(s))
	}
	result := 0
	for i := len(s) - 1; i >= 0; i-- {
		for j := i; j < len(s); j++ { // 注意dp定义 j是不能小于i的
			if s[i] == s[j] {
				if i == j {
					dpArray[i][j] = true
					result += 1
					continue
				}
				if math.Abs(float64(i - j)) == 1 {
					dpArray[i][j] = true
					result += 1
					continue
				}
				dpArray[i][j] = dpArray[i + 1][j - 1]
				if dpArray[i][j] == true {
					result += 1
				}
			}
		}
	}
	return result
}

2 LeetCode516 最长回文子序列

题目

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

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

示例 1：


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

示例 2：


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

提示：

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

有了上一道题的经验之后，这题就相对好想一些。思路大体上是一致的，定义都是关于从s[i]到s[j]这段连续字符串的，这次存储的是这段连续字符串的最长回文串的长度。如果首尾两个地方相同，那么直接在dpArray[i + 1][j - 1]的基础上加2即可，反正可以删除字符，不需要考虑连续问题；如果首尾两个地方不同，那么就该分开考虑要删除谁的问题。删去s[j]，对应的就是dpArray[i][j - 1]；删去s[i]，对应的就是dpArray[i + 1][j]。

go
func longestPalindromeSubseq(s string) int {
	dpArray := make([][]int, len(s))
	for i := range dpArray {
		dpArray[i] = make([]int, len(s))
		dpArray[i][i] = 1
	}
	for i := len(s) - 1; i >= 0; i-- {
		for j := i + 1; j < len(s); j++ {
			if s[i] == s[j] {
				dpArray[i][j] = dpArray[i + 1][j - 1] + 2
			} else {
				dpArray[i][j] = max(dpArray[i + 1][j], dpArray[i][j - 1])
			}
		}
	}
	return dpArray[0][len(s) - 1]
}

最后贴个dp数组的图帮助理解：

目录

1 LeetCode647 回文子串

2 LeetCode516 最长回文子序列