一、题目原型：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
二、题目意思剖析：
回文其实是对称的一个字符串。
比如：aba 、xyx、 mnnm、xoox 这样子。。。
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
输入: "cbbd"
输出: "bb"
三、解题思路：
中心法
官方解释：
事实上，只需使用恒定的空间，我们就可以在 O(n^2) 的时间内解决这个问题。
我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n−1 个这样的中心。
你可能会问，为什么会是 2n−1 个，而不是 n 个中心？原因在于所含字母数为偶数的回文的中心可以处于两字母之间（例如 “abba” 的中心在两个 ‘b’ 之间）。
我的理解：
我们根据对称的这个特性，来进行查找，以一个点为中心，两个指针左右移动，如果两边对应的字母相同，那么就继续移动，直到超出边界或者两边字母不同。
笔记思路.JPG
// 返回当前回文最大的长度
func haha(_ letters: [String],_ left: Int, _ right: Int) -> (Int) {
var L:Int = left
var R: Int = right
// 当左边指针不小于0，当右边指针不超过字符串长度
// 并且左右两个数值要相等
while L>=0 && R<letters.count && letters[L] == letters[R] {
L = L - 1
R = R + 1
}
return R - L - 1
}
func longestPalindrome(_ s: String) -> String {
var letters: [String] = []
for char in s {
let str: String = String.init(char)
letters.append(str)
}
var start:Int = 0
var end: Int = 0
var huiwen: String = ""
for i in 0..<letters.count {
// 这分为两种情况：1.回文长度为奇数时，中心在中间那个字母
// 2.回文长度为偶数时，中心在两个字母之间
let len1: Int = haha(letters, i, i)
let len2: Int = haha(letters, i, i+1)
// 取最大值
let len: Int = len1 > len2 ? len1 : len2
if len > end - start {
start = i - (len - 1) / 2
end = i + len / 2
}
}
for i in start..<end+1 {
huiwen.append(letters[i])
}
return huiwen
}
四、小结
一切一切的算法，前提是要找到规律。然后一步一步剖析找出最好的算法。
在本题中，我的笔记思路只画出了一种情况，还有另一种情况就是回文长度为偶数时，中心在两个字母之间，也是一样的规律去找。最后比较这两种情况，找出最大值就行了。
总提交数.png
提交结果.png
有其他好的方法请极速留言，非常乐意一起探讨。😄
个人博客地址
