1. 判断首尾两个字符是否相同
2. 判断夹在首尾字符中间的子字符串是否为回文字符串
算法小白：这下彻底明白了，不过应该如何保存历史呢？设计算法和实现算法还是有一定差别的，这就是理论派和实践派的差距，中间差了一个特斯拉的距离。
算法君：哈哈，理论与实践是有差别的，但好像也没那么大。其实理论与实践很多时候是相辅相成的。
算法小白：快快，给我讲讲到底如何保存历史，给我一架从理论到实践的梯子吧！
算法君：梯子！没有，我这有一壶凉水，浇下去就灌顶了！
算法小白：别逗了，赶快说说！
算法君：要想确定如何保存历史记录，首先要确定如何获取这些数据，然后再根据获取的方式确定具体的数据结构。我们期望知道字符串中任意的子串是否是回文字符串，这个子串的第一个字符在原字符串中的索引是i，最后一个字符在原字符串中的索引是j。所以我们期望有一个函数is_palindrome_string，通过将i和j作为参数传入该函数，如果i和j确定的字符串是回文，返回true，否则返回false。
算法小白：老大的意思是说将i和j作为查询历史记录的key吗？
算法君：没错，这次终于说对了一回。下面就看is_palindrome_string函数如何实现了！
算法小白：我想想啊，那么如何实现这个is_palindrome_string函数呢？通过key搜索是否为回文的历史记录，也就是搜索value，在Python中字典可以实现这个功能。用字典可以吗？
算法君：字典算是一种实现，你想想用字典具体应该如何实现呢？
算法小白：这个我知道，Python我已经很熟悉了。可以将i和j作为一个列表，然后作为字典的key，不不不，该用元组，Python中是不支持将列表作为字典的key的。
例如：history_record = {(1,1):True, (1,3):False}
算法小白：然后通过元组(i,j)查询历史，例如，要想知道索引从1到3的子串是否为回文字符串，只需要搜索history_record即可，代码如下：
history_record[(1,3)]
算法君：没错，这算是一种存储历史的方法，不过搜索字典仍然需要时间，尽管时间不是线性的。想想还有没有更快的定位历史记录的方法呢？
算法小白：快速定位？..... 这个，比字典还快，难道是用魔法吗？ 哈哈哈！这个还真一时想不出。
算法君：其实在数据结构中，已经清楚地阐述了最快定位的数据结构，这就是数组，由于数组是在内存中的一块连续空间，所以可以根据偏移量瞬间定位到特定的位置。
算法小白：嗯，数组我当然知道，不过如何用数组来保存回文字符串的历史呢？
算法君：前面提到的is_palindrome_string函数有两个参数i和j。i和j是字符串中某一个字符的索引，从0开始，取值范围都是0 <= i,j < n（这里假设字符串的长度是n），其实这也符合二维数组的索引取值规则。假设有一个n*n的正方形二维数组P（每个元素初始值都是0）。如果从i到j的字符串是回文字符串，那么就将P[i,j]设为1，如果要知道从i到j的字符串是否为回文字符串，也只需要查询P[i,j]即可。
算法君：举个具体的例子，有一个字符串acxxcd，要求该字符串的最大回文字符串，可以创建如下图的6*6的二维数组，初始化为0。
然后将长度为1的字符串标记为回文字符串（主对角线上），如P[0,0],P[1,1]等。
接下来将长度为2 的字符串是回文的做一下标记，也就是两个字符相等的字符串，这里只有一个，那就是xx，也就是P[2,3]。如下图所示。
在字符串acxxcd中，并没有长度为3的回文字符串，所以直接搜索长度为4的回文字符串，如果搜索长度为4的字符串，按着前面的描述，先要判断首尾字符是否相等，如果相等，再判断夹在中间的字符串是否为回文字符串，夹在中间的字符串的长度肯定是2，所以可以直接在这个二维数组上定位。例如，搜索到cxxc，首尾字符都是c，中间的xx在二维数组中的坐标是P[2,3]，这个位置刚刚在前面设置为1，所以xx是回文字符串，从而判定cxxc是回文字符串。而cxxc在整个字符串中首尾字符的位置是（1,4)，所以需要将P[1,4]设置为1，如下图所示。
继续扫描长度为5的回文字符串（不存在），然后是长度为6的回文字符串（不存在），所以这个唯一的长度为4的回文字符串就是acxxcd的最长回文字符串。
算法君：这种算法还有一个名字：动态规划法
算法小白：哈哈，还可以这么做。又学了一招！！老大就是老大！
算法君：不过这种存储方案也有缺点，就是比较浪费内存空间，因为需要额外申请n*n的数组空间。另外，你能说出这个算法的时间复杂度和空间复杂度吗？
算法小白：复杂度？我想想，所谓复杂度就是值随着算法输入数据的多少，时间和空间的变化关系吧。如是线性变化的，那么时间复杂度就是O(n)。
算法君：是的，可以这么理解。那么这个算法的复杂度是多少呢？
算法小白：由于该算法需要申请n*n的数组，所以空间复杂度应该是O(n^2），对于每一个字符串，都需要从长度为1的回文字符串开始搜索，需要双重循环，所以时间复杂度也是O(n^2）。
算法君：嗯，这回说得没错，那么还有什么更好的算法可以降低空间复杂度吗？例如，将空间复杂度降为O(1)，也就是不需要申请额外的内存空间。
算法小白：我现在已经用脑过度了，这个要回去好好考虑下。感谢老大耐心讲解。
算法君：好吧，回去多想想还有没有更好的算法。如果想知道这些算法的具体实现细节，可以扫描下面的二维码，并关注“极客起源”公众号，然后输入229893，即可获得相关资源。除此之外，还有更多精彩内容等着你哦！
#动态规划法求最长回文字符串的完整代码
class MaxPalindromeString:
def __init__(self):
self.start_index = None
self.array_len = None
def get_longest_palindrome(self,s):
if s == None:
return
size = len(s)
if size < 1:
return
self.start_index = 0
self.array_len = 1
# 用于保存历史记录（size * size)
history_record = [([0] * size) for i in range(size)]
# 初始化长度为1的回文字符串信息
i= 0
while i< size:
history_record[i][i] = 1
i += 1
# 初始化长度为2的回文字符串信息
i = 0
while i < size - 1:
if s[i] == s[i+1]:
history_record[i][i+1] = 1
self.start_index = i
self.array_len = 2
i += 1
# 查找从长度为3开始的回文字符串
p_len = 3
while p_len <= size:
i = 0
while i < size-p_len + 1:
j = i + p_len-1
if s[i] == s[j] and history_record[i+1][j-1] == 1:
history_record[i][j] = 1
self.start_index = i
self.array_len = p_len
i += 1
p_len += 1
s = ‘abcdefgfedxyz‘
s1 = ‘akbubk‘
p = MaxPalindromeString()
p.get_longest_palindrome(s1)
if p.start_index != -1 and p.array_len != -1:
print(‘最长回文字符串：‘,s1[p.start_index:p.start_index + p.array_len])
else:
print(‘查找失败‘)
