回文系列总结
# 1332. 删除回文子序列 (opens new window)
给你一个字符串
s
,它仅由字母'a'
和'b'
组成。每一次删除操作都可以从s
中删除一个回文 子序列。返回删除给定字符串中所有字符(字符串为空)的最小删除次数。
样例
Input:s = "baabb"
Output:2
解释:"baabb" -> "b" -> "".
先删除回文子序列 "baab",然后再删除 "b"。
也可以
"baabb" -> "bbb" -> ""
2
3
4
5
6
7
思路
因为只由 a
和 b
组成,所以对于任何一个字符串,最多只需要两次就可以完全删除。可以第一次删除全A,第二次删除全B。只需要分为三种情况:空字符是 0,回文串返回 1,非回文串返回 2
代码
class Solution:
def removePalindromeSub(self, s: str) -> int:
if not s: return 0 # 空字符
if s == s[::-1]: # 回文串
return 1
else: # 非回文串
return 2
2
3
4
5
6
7
# 266. 回文排列 (opens new window)
判断该字符串中是否可以通过重新排列组合,形成一个回文字符串。
思路
统计词频,判断是否存在超过2个的奇数词频
代码
import collections
class Solution:
def canPermutePalindrome(self, s: str) -> bool:
word = collections.defaultdict(int)
for char in s:
word[char] += 1
# 0 或 1 个奇数频次
odd = 0
for k, v in word.items():
if v % 2 == 1:
odd += 1
return odd <= 1
2
3
4
5
6
7
8
9
10
11
12
13
# 9. 回文数 (opens new window)
判断一个整数是否是回文数。参考:教程 (opens new window)
思路
- 转换成字符串,判断是否匹配
- 翻转整数,判断是否匹配
- 左右指针,向中间缩
代码
转换成字符串匹配
class Solution: def isPalindrome(self, x: int) -> bool: s = str(x) return s == s[::-1]
1
2
3
4翻转整数,
123 --> 321
func isPalindrome(x int) bool { num := x reverseNum := 0 for x > 0 { reverseNum = reverseNum * 10 + x % 10 // 翻转 x = x / 10 } return num == reverseNum }
1
2
3
4
5
6
7
8
9左右指针,向中间缩
1 23452 1 匹配最左和最右的1
2 345 2 匹配最左和最右的2
3 4 5 匹配左边的3,和右边的5,不等
func isPalindrome(x int) bool { if x < 0 { return false } // 求出数字的位数 digit := 1 for x / digit >= 10 { // 等号容易漏 digit *= 10 } // 1231 求出的 digit 是 1000 for x > 0 { left := x / digit // 1231 -> 1 right := x % 10 // 1231 -> 1 if left != right { return false } x = (x % digit) / 10 // 1231 -> 23 digit = digit / 100 } return true }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 409. 最长回文串 (opens new window)
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。
思路
本题和 266 回文排列 (opens new window) 一样,只是多了统计奇数的个数。当奇数个数大于 0 的时候,减去 奇数的个数 - 1
就可以将字母的出现频率从奇数变成偶数。减一是因为,只允许一个奇数。
func longestPalindrome(s string) int {
word := make(map[rune]int)
for _, char := range s {
word[char]++
}
oddNum := 0
minOddNum := len(s)
for _, v := range word {
if v % 2 == 1 {
oddNum++
if v < minOddNum {
minOddNum = v
}
}
}
var ans int
if oddNum > 0 {
ans = len(s) - (oddNum - 1)
} else {
ans = len(s)
}
return ans
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 125. 验证回文串 (opens new window)
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
样例
Input: "A man, a plan, a canal: Panama"
Output: true
2
代码
func isAlnum (char byte) bool{
return (char >='A' && char <='Z') ||
(char >='a' && char <='z') ||
(char >='0' && char <='9')
}
func isPalindrome(s string) bool {
s = strings.ToLower(s)
for i, j:=0, len(s) - 1; i < j; {
for i < j && !isAlnum(s[i]) { // 排除掉非字母数字的字符
i++
}
for i < j && !isAlnum(s[j]) {
j--
}
if i >= j {
break
}
if s[i] != s[j] {
return false
}
i++
j--
}
return true
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 680. 验证回文字符串 Ⅱ (opens new window)
给定一个非空字符串
s
,最多删除一个字符。判断是否能成为回文字符串。
思路: 使用递归分情况判断
代码
func isPalindrome(s string, i, j int) bool {
for i < j {
if s[i] != s[j] {
return false
}
i++
j--
}
return true
}
func validPalindrome(s string) bool {
if len(s) == 0 || len(s) == 1 {
return true
}
for i, j:= 0, len(s) - 1; i < j;{
if s[i] == s[j] {
i++
j--
} else {
return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1)
}
}
return true
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 131. 分割回文串 (opens new window)
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
输入 "aab" 返回 [ ["aa","b"], ["a","a","b"]]
思路:使用回溯算法的切割问题
代码
def backtracking(s, ans, startIndex, tmp):
if startIndex >= len(s):
ans.append(tmp[:])
for i in range(startIndex, len(s)):
if isValid(s[startIndex: i + 1]):
tmp.append(s[startIndex: i + 1]) # 切割
backtracking(s, ans, i + 1, tmp)
tmp.pop()
def isValid(s):
""" 验证是否是回文字符串 """
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
class Solution:
def partition(self, s: str) -> List[List[str]]:
ans = []
backtracking(s, ans, 0, [])
return ans
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 1457. 二叉树中的伪回文路径 (opens new window)
根到叶子节点的所有路径中 伪回文 路径的数目。
思路: 二叉树遍历 + 266.回文排列 结合
代码
func isPseudoPalindromic() bool{ // 226 回文排列 判断是否回文排列
oddNum := 0
for _, v := range nodeDict {
if v % 2 == 1 {
oddNum++
}
}
return oddNum < 2
}
func dfs(root * TreeNode) {
if root == nil {
return
}
nodeDict[root.Val]++
if root.Left == nil && root.Right == nil { // 如果是叶子节点
if isPseudoPalindromic(){
ans++
}
}
dfs(root.Left)
dfs(root.Right)
nodeDict[root.Val]--
}
var nodeDict map[int]int // 全局变量
var ans int
func pseudoPalindromicPaths (root *TreeNode) int {
nodeDict = make(map[int]int, 10)
ans = 0
dfs(root) // 遍历
return ans
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 647. 回文子串(Medium) (opens new window)
计算这个字符串中有多少个回文子串。
思路1:两层循环遍历,判断是否是回文串。时间复杂度 $O(n^3)$
var ans int
func isPalindrome(s string, i, j int) bool {
for i < j {
if s[i] != s[j] {
return false
}
i++
j--
}
return true
}
func countSubstrings(s string) int {
ans = 0
for i:= 0; i < len(s); i++ {
for j:= i; j < len(s); j++ {
if isPalindrome(s, i, j) {
ans++
}
}
}
return ans
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
思路2:动态规划
从基础情况向外扩展,dp[i][j]
记录了 i, j 区间是否是回文串
func countSubstrings(s string) int {
dp := make([][]bool, len(s))
for i:= 0; i < len(s); i++ {
dp[i] = make([]bool, len(s))
}
count := 0
for j:= 0; j < len(s); j++ { //遍历的顺序要注意
for i:= 0; i <= j; i++ {
if i == j { // 基础情况1: aba 中间元素是奇数次
dp[i][j] = true
count++
} else if j - i == 1 && s[i] == s[j] { // 基础情况1: aa 没有中间元素
dp[i][j] = true
count++
} else if j - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]{ // 扩展
dp[i][j] = true
count++
}
}
}
return count
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 516. 最长回文子序列(Medium) (opens new window)
找到给定字符串s 的最长的回文子序列,并返回其最大长度
之前写的解答: 516. 最长回文子序列(Medium)
思路1:在125.验证回文串的基础上进行修改,在判断条件上,当 s[i] != s[j] 的时候,调过左边指针或者右边指针。使用递归实现比较简单
var ans int
func longestPalindromeSubseq(s string) int {
if len(s) < 2 {
return len(s)
}
ans = 1
for i:= 0; i < len(s); i++ {
expendAroundCenter(s, i - 1, i + 1, 0)
expendAroundCenter(s, i, i + 1, 0)
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func expendAroundCenter(s string, start int, end int , deleteLetter int ) {
if start < 0 || end >= len(s) {
return
}
if s[start] == s[end] {
ans = max(ans, end - start + 1 - deleteLetter)
expendAroundCenter(s, start - 1, end + 1, deleteLetter)
} else {
expendAroundCenter(s, start, end + 1, deleteLetter + 1)
expendAroundCenter(s, start - 1, end, deleteLetter + 1)
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
思路2:动态规划
func max(a,b int) int {
if a > b {
return a
}
return b
}
func longestPalindromeSubseq(s string) int {
n := len(s)
if n < 2 {
return n
}
dp := make([][]int, n)
for i:= 0; i < n; i++ {
dp[i] = make([]int, n)
}
for i:= n - 1; i >= 0; i-- { // 必须保证 i 计算的时候, i + 1 已经计算好了 ==> 从右向左
dp[i][i] = 1 // 只有一个字符长度为 1
for j:= i + 1; j < n; j++ { // 必须保证 j 计算的时候,j - 1 已经计算好了 ==> 从左向右
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][n - 1]
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 267. 回文排列 II(Medium) (opens new window)
给定字符串 s ,返回重新排列组合后所有可能的回文字符串。并去除所有重复的组合。
如输入 "aabb",返回 ["abba", "baab"]。如果不能形成任何回文排列时,则返回一个空列表。
本题前半部分实现验证回文串,同 125.验证回文串一样。后半部分的难点在于,如何去重。
思路1:使用哈希表去重
def backtracing(s, ans, count, tmp):
if len(tmp) == len(s): # 找到答案
ans.append(tmp)
return
for k, v in count.items():
if v > 0:
newTmp = k + tmp + k
count[k] -= 2
backtracing(s, ans, count, newTmp)
count[k] += 2 # 状态回溯
class Solution:
def generatePalindromes(self, s: str) -> List[str]:
# 1. 检查是否能够组成回文字符
count = collections.defaultdict(int)
for char in s: # 哈希表
count[char] += 1
oddNum = 0
oddString = ""
for k, v in count.items():
if v % 2 == 1:
oddNum += 1
oddString = k
if oddNum > 1 : # 不是回文字符串
return []
if oddString != "": # 如果有奇数字符串的话,就放中间,很容易漏掉
count[oddString] -= 1
# 2. 求出所有组合
ans = []
backtracing(s, ans, count, oddString)
return ans
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 1328. 破坏回文串 (opens new window)
给你一个回文字符串 ,请你将其中 一个 字符用任意小写英文字母替换,使得结果字符串的字典序最小,且 不是 回文串。如果无法做到,则返回一个空串。
输入 "abccba" 返回 "aaccba"
思路: 总结规律
代码
/*
规律总结
1. 当长度小于等于1 一定是回文串,返回 ""
2. 当前半部分存在非 a 的字符,修改成a,返回
3. 当前半部分都是a,直接修改最后一个字符为 b
*/
func breakPalindrome(palindrome string) string {
ans := strings.Split(palindrome, "") // 字符串切分为 字符数组
n := len(palindrome)
if n < 2 {
return ""
}
var flag bool
for i := 0; i < n / 2; i++ {
if ans[i] != "a" {
ans[i] = "a"
flag = true
break
}
}
if flag { // 2. 当前半部分存在非 a 的字符,修改成a,返回
return strings.Join(ans, "")
} else { // 3. 当前半部分都是a,直接修改最后一个字符为 b
ans[len(ans) - 1] = "b"
return strings.Join(ans, "")
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 1216. 验证回文字符串 III(Hard) (opens new window)
判断,是否能从 s 中最多删除 k 个元素,可以形成 回文字符串
本质上就是求出最长回文子序列,虽说是 Hard,但是本质上,就是 516.最长回文子序列
代码
func max(a, b int) int {
if a > b {
return a
}
return b
}
// 516.最长回文子序列
func longestPalindromeSubseq(s string) int {
if len(s) < 2 {
return len(s)
}
dp := make([][]int, len(s))
for i:= 0; i < len(s); i++ {
dp[i] = make([]int, len(s))
}
for i := len(s) - 1; i >= 0 ; i-- {
for j := i; j < len(s); j++ {
if i == j { // 基础情形
dp[i][j] = 1
} else 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]) // 推出 i 是从右向左 j 是从下向上
}
}
}
return dp[0][len(s) - 1]
}
func isValidPalindrome(s string, k int) bool {
vaildLength := longestPalindromeSubseq(s)
return len(s) - vaildLength <= k
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 1177. 构建回文串检测(Medium) (opens new window)
检查 s 的子串是不是符合条件,给定三个数(left, right, k), 判断能不能在至多替换 k 个字母的情况下,使得 s[left, right+1] 子串的任意排列成为回文串
思路:
本题算是上面众多题目的集合,用我们原先 哈希 + 奇数个数 < 2
的方法去做可以简单套用,但是无法会超时,原因是多次计算哈希表很耗时,而且有很多的重复计算。我们可以把哈希表的计算中间结果保存,减少重复计算。 这里参考了 这个教程 (opens new window)
// 超时 29 / 31
func isPailWord(s string, left int, right int, k int) bool {
count := make(map[byte]int, right - left + 1)
for i := left; i <= right; i++ { // 这里count重复计算了
count[s[i]]++
}
oddNum := 0
for _, v := range count {
if v % 2 == 1 {
oddNum++
}
}
return oddNum - k * 2 < 2 // k 是更改,一个抵两个用 如 abc -> aba 奇数从 3 变成 2
}
func canMakePaliQueries(s string, queries [][]int) []bool {
ans := make([]bool, len(queries))
for i := 0; i < len(queries); i++ {
subAns := isPailWord(s, queries[i][0], queries[i][1], queries[i][2])
ans[i] = subAns
}
return ans
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
使用动态规划,优化哈希表的查询效率
func isPailWord(s string, left int, right int, k int) bool {
oddNum := 0
tempNum := 0
for i := 0; i < 26; i++ {
if left == 0 { // 对于最左侧的元素特殊处理
tempNum = dp[right][i] - 0
} else {
tempNum = dp[right][i] - dp[left - 1][i]
}
if tempNum % 2 == 1 {
oddNum++
}
}
return oddNum - k * 2 < 2
}
var dp [][]int
func canMakePaliQueries(s string, queries [][]int) []bool {
// dp[i][j] i 记录的是前i个索引中j的词频
dp = make([][]int, len(s))
for i:= 0; i < len(s); i++ {
dp[i] = make([]int, 26) // 26个字母
}
for i, char := range s { // 只遍历一遍统计词频
if i > 0 {
copy(dp[i], dp[i - 1]) // 记录前面的状态,一定要注意是值复制
}
dp[i][char - 'a']++
}
ans := make([]bool, len(queries))
for i := 0; i < len(queries); i++ {
subAns := isPailWord(s, queries[i][0], queries[i][1], queries[i][2])
ans[i] = subAns
}
return ans
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41