跳到主要内容

回文系列总结

1332. 删除回文子序列​

给你一个字符串 s，它仅由字母 'a' 和 'b' 组成。每一次删除操作都可以从 s 中删除一个回文 子序列。返回删除给定字符串中所有字符（字符串为空）的最小删除次数。

样例

Input：s = "baabb"
Output：2
解释："baabb" -> "b" -> "". 
先删除回文子序列 "baab"，然后再删除 "b"。

也可以 
"baabb" -> "bbb" -> ""

思路

因为只由 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

266. 回文排列​

判断该字符串中是否可以通过重新排列组合，形成一个回文字符串。

思路

统计词频，判断是否存在超过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

9. 回文数​

判断一个整数是否是回文数。参考：教程

思路

  1. 转换成字符串，判断是否匹配
  2. 翻转整数，判断是否匹配
  3. 左右指针，向中间缩

代码

  1. 转换成字符串匹配

    class Solution:
        def isPalindrome(self, x: int) -> bool:
            s = str(x)
            return s == s[::-1]

  2. 翻转整数，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
    }

  3. 左右指针，向中间缩

    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 
    }

409. 最长回文串​

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

思路

本题和 266 回文排列 一样，只是多了统计奇数的个数。当奇数个数大于 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 
}

125. 验证回文串​

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

样例

Input: "A man, a plan, a canal: Panama"
Output: true

代码

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 
}

680. 验证回文字符串 Ⅱ​

给定一个非空字符串 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 
}

131. 分割回文串​

给定一个字符串 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

1457. 二叉树中的伪回文路径​

根到叶子节点的所有路径中 伪回文 路径的数目。

思路： 二叉树遍历 + 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
}

647. 回文子串(Medium)​

计算这个字符串中有多少个回文子串。

思路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：动态规划

从基础情况向外扩展，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 
}

516. 最长回文子序列(Medium)​

找到给定字符串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：动态规划

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]
}

267. 回文排列 II(Medium)​

给定字符串 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

1328. 破坏回文串​

给你一个回文字符串 ，请你将其中 一个 字符用任意小写英文字母替换，使得结果字符串的字典序最小，且 不是 回文串。如果无法做到，则返回一个空串。

输入 "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, "")
    }
}

1216. 验证回文字符串 III(Hard)​

判断，是否能从 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 
}

1177. 构建回文串检测(Medium)​

检查 s 的子串是不是符合条件，给定三个数(left, right, k)， 判断能不能在至多替换 k 个字母的情况下，使得 s[left, right+1] 子串的任意排列成为回文串

思路：

本题算是上面众多题目的集合，用我们原先 哈希 + 奇数个数 < 2 的方法去做可以简单套用，但是无法会超时，原因是多次计算哈希表很耗时，而且有很多的重复计算。我们可以把哈希表的计算中间结果保存，减少重复计算。 这里参考了 这个教程

// 超时 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 
}

使用动态规划，优化哈希表的查询效率

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 
}