回文数子串

回文数概念

回文是指正读反读都能读通的句子，如“我为人人，人人为我”等。在数学中也有这样一类数字有这样的特征，成为回文数。

中心扩展法

中心扩展法就是字面意思，从中间向两端扩展，判断字符是否一致，进行遍历。

回文数字串

采用中心扩展法来获取，但是会存在奇数和偶数的回文子串，所以这两种方法需要分开考虑。
第一种

  /**
 * @param {string} s
 * @return {string}
 */
function longestPalindrome(s) {
    
    const len = s.length;
    if (len < 2) return s;
    
    let max = 1;
    let resultStr = s.substr(0, 1);
     
    // 奇数扩展法
    for (let i = 0; i < len; i += 1) {
        let start = i - 1;
        let end = i + 1;
        
        while (start >= 0 && end < len && s.charAt(start) === s.charAt(end)) {
            start -= 1;
            end += 1;
        }
        
        if ((end - 1) - (start + 1) + 1 > max) {
            max = (end - 1) - (start + 1) + 1;
            resultStr = s.substr(start + 1, max);
        }
    }
    
    // 偶数扩展法
    for (let i = 0; i < len; i += 1) {
        let start = i;
        let end = i + 1;
        
        while (start >= 0 && end < len && s.charAt(start) === s.charAt(end)) {
            start -= 1;
            end += 1;
        }
        
        if ((end - 1) - (start + 1) + 1 > max) {
            max = (end - 1) - (start + 1) + 1;
            resultStr = s.substr(start + 1, max);
        }
    }
    
    return resultStr;
    
};

let  s = 'babad';
longestPalindrome(s); // bab

第二种

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let curNum = 0,maxLen = 1;
    for( let i = 0; i < s.length;i++) {
        const len1 = getNum(s, i, i);
        const len2 = getNum(s, i, i+1);
        const max = Math.max(len1, len2);
        if(max > maxLen) {
            maxLen = max;
            curNum = i - (max-1)/2;
            curNum = len1 > len2 ? curNum : curNum+1
        }
    }
    return s.substr(curNum,maxLen)
};
            
function getNum(s, left,right) {
    while(left >= 0 && right < s.length && s[left] === s[right]) {
        left--;
        right++;
    } 
    return right -left - 1;
}
let  s = 'babad';
longestPalindrome(s); // bab

github算法地址