[ALGORITHM] Dynamic programming – find the longest loop substring

Palindromes are symmetrical strings, such as ABA, ABccba

Question: Given a string, return the longest callback substring

The axis of symmetry is the center, so you can use “center diffusion”, or “dynamic programming”. (Note: To distinguish between odd and even)

/ * * *@param {string} s
 * @return {string}* /
var getLongestHuiwen = function(s) {
    if (s.length === 1) return s
    let max = ' '

    for (let i = 0; i < s.length-1; i++) {
        let odd = centerSpread(s, i, i)
        let even = centerSpread(s, i, i+1)
        if (odd.length > even.length) {
            if (odd.length > max.length) {
                max = odd
            }
        } else {
            if (even.length > max.length) {
                max = even
            }
        }
    }
    return max
};

function centerSpread(s, left, right) {
    let max = ' '
    while(left >= 0 && right < s.length) {
        if (s.charAt(left) === s.charAt(right)) {
            left--
            right++
        } else {
            break
        }
    }
     left++
     right--
    max = s.slice(left, right + 1)
    // console.log(max, left)
    return max
}
Copy the code