关于javascript:Leetcode-5-最长回文子串

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

示例 1：

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

示例 2：

输出：s = “cbbd”
输入：”bb”

示例 3：

输出：s = “a”
输入：”a”

示例 4：

输出：s = “ac”
输入：”a”

解题思路

应用动静布局，状态转移方程如下：

dp[i][j] = (s[i] == s[j]) && (i - j < 3 || dp[j + 1][i - 1])

如果呈现 s[i] == s[j]，则如果满足 i - j < 3 或者 dp[j + 1][i - 1] 也是回文串，那么从 j 到 i 这个区间的字符串也是回文串。

i - j < 3 对应三种状况，第一种是三个字符，首尾雷同，两头不论是什么字符，都是回文串，第二种是两个字符，都雷同，显然也是回文串，第三种是只有一个字符，一个字符自身也是回文串

Java 实现：

class Solution {public String longestPalindrome(String s) {if (s == null || s.length() == 0) return s;
        int len = s.length();
        int start = 0;
        int maxLen = 1;
        boolean[][] dp = new boolean[len][len];
        for (int i=0; i<len; i++) {for (int j=0; j<=i; j++) {if (i == j) {
                    // 初始条件
                    // 一个字符自身就是回文串
                    dp[i][i] = true;
                    continue;
                }
                if (s.charAt(i) == s.charAt(j)) {if (i - j <= 2 || dp[j + 1][i - 1]) {
                        // 状态转移方程
                        dp[j][i] = true;
                        if (i - j + 1 > maxLen) {
                            // 记录最大长度和起始下标
                            maxLen = i - j + 1;
                            start = j;
                        }
                    }
                }
            }
        }
        // 返回字符串
        return s.substring(start, start + maxLen);
    }
}

JS 实现：

function longestPalindrome(s) {if (s == null || s.length == 0) return s;
    let len = s.length;
    let start = 0;
    let maxLen = 1;
    let dp = gen2DArray(len, len);
    for (let i=0; i<s.length; i++) {for (let j=0; j<=i; j++) {if (i == j) {dp[i][i] = true;
                continue;
            }
            if (s[i] == s[j]) {if (i - j <= 2 || dp[j + 1][i - 1]) {dp[j][i] = true;
                    if (i - j + 1 > maxLen) {
                        maxLen = i - j + 1;
                        start = j;
                    }
                }
            }
        }
    }
    return s.substring(start, start + maxLen)
}

function gen2DArray(a, b) {let res = [];
    for (let i=0; i<a; i++) {res.push([]);
        for (let j=0; j<b; j++) {res[i][j] = false;
        }
    }
    return res;
}