LeetCode算法题-5. 最长回文子串（Swift）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring

题目

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

示例 1：

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

示例 2：

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

正读和反读都相同的字符序列为“回文”，如“abba”、“abcba”是“回文”。"abc"这种不是。也可以说是字符串反转后和原字符串是一样的

方法

class Solution {
    func longestPalindrome(_ s: String) -> String {
        if s.count == 0 || s.count == 1 {
            return s
        }
        let charArray = [Character](s)
        var isPalindrome = [[Bool]](repeating: [Bool](repeating: false, count: charArray.count), count: charArray.count)
        for i in 0..<charArray.count {
            isPalindrome[i][i] = true
        }
        for i in 0..<charArray.count - 1 {
            if charArray[i] == charArray[i + 1] {
                isPalindrome[i][i + 1] = true
            }
        }
        var left = 0
        var right = 0
        for j in 1..<charArray.count {
            for i in 0..<j {
                if charArray[i] == charArray[j] && (isPalindrome[i + 1][j - 1] || j - i <= 2) {
                    isPalindrome[i][j] = true
                    if j - i > right - left {
                        left = i
                        right = j
                    }
                }
            }
        }
        return String(charArray[left...right])
    }
}