前端算法--回文串

题目描述：

给你一个整数 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

解法：

对于回文数或者说是回文字符串，可以理解成一个字符串正着都和反着读结果是一样的。

例如：abcba，正着读结果是：a->b->c->b->a，反着读结果是：a<-b<-c<-b<-a，他们的结果是一样的。

例如：上海自来水来自海上也是一个回文字符串。

首先把字符串转换成一个字符数组，然后可以利用头尾依次比较的思想，分别指向头和尾的元素，判断他们是否相等。

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    // 特殊情况
    if (x < 0) return false
    if (x == 1) return true

    x = x.toString()

    var mid = parseInt(x.length/2) // 不用遍历全部，只需要遍历到中间元素即可，因为后面的已经比较过了
    for (var i = 0 ; i < mid ; i++) {
        if (x[i] != x[x.length-1-i]) {// 头尾两个元素比较
            return false
        }
    }

    return true
};

在了解了回文字符串之后，来看下面一道题，求一个字符串的最长回文子串。

题目描述

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

示例 1：

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

示例 2：

输入：s = "cbbd"
输出："bb"

示例 3：

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

示例 4：

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

解法：

首先，对于子串的定义我们需要明白它的涵义是：字符串中一段连续的子字符串，例如字符串abcde中，其中abc是其子串，abcd也是，而ac或者bd就不是，因为他们不连续。

同时，通过上一题的思路，我们可以很容易得到一种暴力的解法，即枚举求出改字符串的所有子串，然后分别判断他们是否是回文串，同时记录长度，取最大长度的结果，我们可以得到如下解法：

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    // 单个字符必然是回文串
    if (s.length == 1) return s
    // 判断是否是回文串
    var check = function(str){
        var mid = parseInt(str.length/2)

        for (var i = 0 ; i < mid ; i++) {
            if (str[i] != str[str.length-i-1]) {
                return false
            }
        }

        return true

    }
    var res = ''
    //枚举出所有子串
    for (var i = 0 ; i < s.length ; i++) {
        var cur = s[i]
        for (var j = i+1 ; j < s.length ; j++) {
            cur = cur + '' + s[j]
            if (check(cur)) {

                if (cur.length > res.length) { // 每次取长度的较大值
                    res = cur
                }
            }
        }
    }

    return res == '' ? s[0] : res
};

上面解法可以通过，但是效率很低，通过观察回文串的特点我们可以知道，对于一个子串而言，如果它是回文串，并且长度大于2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串ababa，如果我们已经知道 bab 是回文串，那么ababa 一定是回文串，这是因为它的首尾两个字母都是a。

创建一个动态规划数组dp[]：

• dp[i][j]表示字符串s[i]到s[j]之间的是否为回文串。
• 并且如果s[i] == s[j]，则dp[i][j] == dp[i+1][j-1]，即如果首位元素相同，那么去掉首位元素后，仍然是回文串。
• 每次更新完dp[i][j]之后，更新并记录最大值。

代码如下：

var longestPalindrome = function(s) {
    let n = s.length;
    let res = '';
    let dp = Array.from(new Array(n),() => new Array(n).fill(0));
    //考虑到 主要的递推关系 是由已知子串 i+1..j-1 的情况， 递推到 i..j 的情况， 因此，迭代过程需要反序迭代变量 i ，正序迭代 j
    for(let i = n-1;i >= 0;i--){
        for(let j = i;j < n;j++){//(j - i < 2)单个字符肯定是回文串 
            //dp[i+1][j-1] 且 s[i] == s[j] 则dp[i][j]肯定是回文串
            if (s[i] == s[j] && (j - i < 2 || dp[i+1][j-1])) {
                dp[i][j] = true
            }
            // 如果dp[i][j]是回文 就记录最大的值(j - i +1)表示长度
            if(dp[i][j] && j - i +1 > res.length){
                res = s.substring(i,j+1);
            }
        }
    }
    return res;
};