FE

# 回文串

跟回文串相关的题目基本都离开不动态规划

# 题

# 9. 回文数 (opens new window)

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

示例 1：
输入：x = 121
输出：true

示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

示例 4：
输入：x = -101
输出：false

解一：

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    x+=''
    let start=0, end=x.length-1
    while(start<end){
        if(x[start] === x[end]){
            start++
            end--
        } else {
            return false
        }
    }
    return true
};

解二：

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    if(x < 0) return false
    let _x = x
    let result = 0
    while(_x){
        result = result*10+_x%10
        _x = (_x/10)|0
    }
    return result === x? true: false
};

# 最长回文子序列 (opens new window)

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1:
输入:"bbbab"
输出:4
一个可能的最长回文子序列为 "bbbb"。

示例 2:
输入:"cbbd"
输出:2
一个可能的最长回文子序列为 "bb"。

解题思路

对于字符串 s 假设 dp[i][j] 表示数组下标 i-j 之间最长回文子序列

那么计算 dp[m][n] 的最长子序列的方式有几种情况：

  1. s[m]===s[n]，那么 dp[m][n] = dp[m+1][n-1]+2

  2. s[m]!==s[n]，那么 dp[m][n] 取现在有区间的最长回文子序列的最大值，dp[m][n] 之间的最大区间有 dp[m+][n] 和 dp[m][n-1]，所以此时 dp[m][n] = Math.max(dp[m+1][n], dp[m][n-1])

  3. 要得到dp[m][n]，得从dp[0][0] 开始计算到 dp[m][n]

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function(s) {
    let dp = new Array(s.length).fill('').map(() => new Array(s.length)) // 定义 dp
    for(let n = 0; n<s.length;n++){ // 从头开始遍历
        for(let m = n;m>=0;m--){ // 外层的值依赖内层的值，所以从里到外遍历
            if(m===n){ // 坐标相等，表示同一个数，dp[m][n] = 1
                dp[m][n] = 1
            } else if(s[m] === s[n]){  // 字符相等
                dp[m][n] = (n-m===1) ? 2: dp[m+1][n-1]+2 // 如果是相邻的字符 dp[m][n] = 2，否则 [m][n] = dp[m+1][n-1]+2
            } else{
                dp[m][n] = Math.max(dp[m+1][n], dp[m][n-1]) // 取[m-n] 区域内的最大值
            }
        }
    }
    return dp[0][s.length-1]
};

# 5. 最长回文子串 (opens new window)

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
示例 3：

输入：s = "a"
输出："a"
示例 4：

输入：s = "ac"
输出："a"

解题思路

此题思路跟 [最长回文子序列] 一样，要解得最长回文字串，那么就得知道哪些是回文串，所以对于字符串 s 定义 dp[i][j]，表示数组下标 i到j 之间是否是回文串

那么计算 dp[m][n] 是否是回文串的情况有有：

  1. s[m]===s[n] && dp[m+1][n-1]

  2. s[m]===s[n] && (n-m<2)， n-m=0 表示 s[m] 和 s[n] 是同一个数，n-m=1 表示 s[m] 和 s[n] 是两个相邻的数，

  3. 要得到dp[m][n]，得从dp[0][0] 开始计算到 dp[m][n]

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let res = ''
    let db = new Array(s.length).fill('').map(() => new Array(s.length))
    for(let i=0; i<s.length;i++){
        for(let j=i;j>=0;j--){
            if(s[i] === s[j]&&(i-j)<2){
                db[j][i] = true
            } else if(s[i] === s[j]&&db[j+1][i-1]){
                db[j][i] = true
            }
            if(db[j][i] && (i-j+1)>res.length){ // 如果是回文串，取这个回文串如果比 res 大的话，就进行保存
                res = s.substring(j,i+1)
            }
        }    
    }
    return res
};

# 647. 回文子串 (opens new window)

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。  
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

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

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

思路

要获取多少回文子串，那么我需要知道两个条件

  1. 这个字符串可以分成哪些子串

  2. 字符串两两之间是否回文串

对于第二点，其实就同 [5. 最长回文子串] 题目一样，建立 dp，计算得到所有的 dp[m][n] 是否是回文串

// 建立 dp 的代码
var countSubstrings = function(s) {
    let dp = new Array(s.length).fill('').map(() => new Array(s.length))
    for(let i=0; i<s.length;i++){
        for(let j=i;j>=0;j--){
            if(s[i] === s[j]&&(i-j)<2){
                dp[j][i] = true
            } else if(s[i] === s[j]&&dp[j+1][i-1]){
                dp[j][i] = true
            }
        }    
    }
};

对于子串，其实循环时得到的dp[j][i]时，[j][i] 就是子串了，所以这题其实这题跟 [5. 最长回文子串] 就是一样的

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    let count = 0
    let dp = new Array(s.length).fill('').map(() => new Array(s.length))
    for(let i=0; i<s.length;i++){
        for(let j=i;j>=0;j--){
            if(s[i] === s[j]&&(i-j)<2){
                dp[j][i] = true
            } else if(s[i] === s[j]&&dp[j+1][i-1]){
                dp[j][i] = true
            }
            if(dp[j][i]){
                count++
            }
        }    
    }
    return count
};

# 131. 分割回文串 (opens new window)

动态规则+回溯

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：

输入：s = "a"
输出：[["a"]]

思路

跟之前的题目类似，得先定义 dp 得到所有两两字符是否是回文串

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
    let bp = new Array(s.length).fill('').map(() => new Array(s.length))
    for(let i = s.length-1;i>=0;i--){
        for(let j = i;j<s.length;j++){
            if(j-i<2 && s[i]===s[j]){
                bp[i][j] = true
            } else if(bp[i+1][j-1] && s[i]===s[j]){
                bp[i][j] = true
            } else{
                bp[i][j] = false
            }
        }
    }
    let res = []
    let tem = []
    let walk = (start) => {
        if(start === s.length){
            res.push([...tem])
            return
        }
        for(let i=start; i<s.length;i++){
            if(!bp[start][i]){
                continue
            }
            tem.push(s.substring(start,i+1))
            walk(i+1)
            tem.pop()
      }
    }
    walk(0)
    return res
}

动态规划详解 (opens new window)

动态规划详解（修订版） (opens new window)

手把手刷动态规划 (opens new window)

← 二叉树 →