5. 最长回文子串

[Hinsverson]

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-palindromic-substring 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[Hinsverson]

暴力：枚举所有长度大于等于 2 的子串，依次判断它们是否是回文

public class Solution {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // s.charAt(i) 每次都会检查数组下标越界，因此先转换成字符数组
        char[] charArray = s.toCharArray();

        // 枚举所有长度大于 1 的子串 charArray[i..j]
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    /**
     * 验证子串 s[left..right] 是否为回文串
     */
    private boolean validPalindromic(char[] charArray, int left, int right) {
        while (left < right) {
            if (charArray[left] != charArray[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

DP：dp[i][j] 则表示 s[i,j] 区间 的子串 是否是回文串，存储的是 布尔值

1. 对于 字符串 s , 长度为 n, 我们定义 一个 dp 数组，大小为 n * n
2. dp[i][j] 则表示 s[i,j] 区间 的子串 是否是回文串，存储的是 布尔值。
3. 为了实现dp递推效果，从左往右我们是按照先固定列j，然后从上到下填行i的顺序去更新dp表，因为只有先把行列角标都比较小的范围内子串判定出来后才能判定大的，因为大的的判断依赖于小的。

class Solution {
    func longestPalindrome(_ s: String) -> String {

        guard s.count > 1 else {
            return s
        }

        var chars = Array(s)

        var dp = Array(repeating: Array(repeating: false, count: s.count), count: s.count)

        var begin = 0
        var maxLength = 1

        for j in 0..<chars.count {

            for i in 0..<j {

                if chars[i] == chars[j] {

                    if (j - 1) - (i + 1) + 1 < 2 { //如果i到j的开区间范围内只有0或者1个元素，那么在i和j位置上数相同的情况下范围内肯定是回文串
                        dp[i][j] = true
                    } else { //大于1个元素的情况下就需要转移缩小范围看内部是否是回文串
                        dp[i][j] = dp[i + 1][j - 1]
                    }

                } //本身i和j数都不等的话肯定不是回文，这里没写else因为上面dp表默认就是false。

                //是回文串时更新答案
                if dp[i][j] && j - i + 1 > maxLength {
                    maxLength = j - i + 1
                    begin = i
                }
            }
        }

        return String(chars[begin..<begin+maxLength])
    }
}