经典算法题 – 最长回文子串（Longeset Palindomic Substring）

讨论一下

今天不讲什么移动端应用的开发技巧啦！
今天咱们来讲讲最长回文子串（Longeset Palindomic Substring）。

最近开始用Python来进行leetcode上的解题，不经怀疑起一个问题：

以前用C（C++）来做题到底是怎么坚持下来的？

果然，Python果然是一门比较简单好懂的脚本语言，之前学过的脚本语言是Javascript，但是感觉语法比较杂糅（大概率认为是脚本语言的通病），所以也就在写前端页面的时候用到过（还有AE的表达式，etc）。
以后希望多多在一些简单的地方使用Python吧。

正文

这道leetcode上序号为第5的题描述如下：

5. 最长回文子串

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

示例 1：

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

示例 2：

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

解法1: 中心扩散法

首先，我们来思考题目的主要描述，以及回文子串的基本特征。
要检验一个字符串是否是回文，那么先找到它的中心字符（index = i），然后使两个指针变量分别指向它的左边（index = i - 1）以及它的右边（index = i + 1）处，判断这两个字符是否相同。然后再判断更左边（index = i - 2）以及它的更右边（index = i + 2）是否相同，一直到第（str[i-k] ）和第（str[i+k]）个字符...

那么，我们可以构造一个循环，不停地来做这件事情：

我们从长度为n的字符串的头部开始，以第i个字符为中心，每次令i自增1：
- 倘若i - k处和i + k处的字符相同：计算length = （i + k）-（i - k）= 2k，比较length与maxLength的大小并记录，再重复这步，直到 i - k < 0 或者 i + k > n - 1 ；
- 倘若i - k处和i + k处的字符不同：中止判断循环；
- 重复以上步骤，每次令k自增1。
重复以上步骤，令i自增1，直到i > n - 1。

是不是听上去很简单，我们只要2个循环就可以完成这项工作啦！
但是！别忘了我们还有类似“abba”这样的回文字符串，它可并没有什么中心字符！

我们可以这样做，我们现在不每次移动1个字符了，我们移动0.5个字符。
听上去好像很奇怪的样子，也就是说，从index = i处开始，我们还是看它的左边与右边，而这次呢，观察的是左边（index = ceil(i - 1)）处，意为小于等于i的最大整数。如果i是整数，和上面的方法没有区别，而i不是整数时，左边还是最靠近i处的左字符，而右边同理，为（index = floor(i + 1)）处，意味大于等于i的最小整数。

所以，我们需要改进一下我们的方法：

我们从长度为n的字符串的头部开始，取i处为中心，每次令k自增1：
- 倘若ceil(i - k)处和floor(i + k)处的字符相同：计算length = （i + k）-（i - k）= 2k，比较length与maxLength的大小并记录，再重复这步，直到 ceil(i - k) < 0 或者 floor(i + k) > n - 1 ；
- 倘若ceil(i - k)处和floor(i + k)处的字符不同：中止判断循环。
重复上一步，令i自增0.5，直到i > n - 1。

完整的代码在这里。

import math

class Solution:
    def longestPalindrome(self, s: str) -> str:

        maxLength = -1
        maxLeft = 0
        maxRight = 0

        i = 0
        while i < len(s):

            length = 0

            k = 1

            while math.ceil(i - k) >= 0 and math.floor(i + k) < len(s):

                if s[math.ceil(i - k)] != s[math.floor(i + k)]:
                    break

                length += math.floor(i + k) - math.ceil(i - k) + 1

                if maxLength < length:
                    maxLength = length
                    maxLeft = math.ceil(i - k)
                    maxRight = math.floor(i + k)

                k += 1

            i += 0.5

        return s[maxLeft:maxRight + 1]


s = "abba"
solution = Solution()
print(solution.longestPalindrome(s))

import math

class Solution:

def longestPalindrome(self, s: str) -> str:

maxLength = -1

maxLeft = 0

maxRight = 0

i = 0

while i < len(s):

length = 0

k = 1

while math.ceil(i - k) >= 0 and math.floor(i + k) < len(s):

if s[math.ceil(i - k)] != s[math.floor(i + k)]:

break

length += math.floor(i + k) - math.ceil(i - k) + 1

if maxLength < length:

maxLength = length

maxLeft = math.ceil(i - k)

maxRight = math.floor(i + k)

k += 1

i += 0.5

return s[maxLeft:maxRight + 1]

s = "abba"

solution = Solution()

print(solution.longestPalindrome(s))

解法2: 动态规划

关于动态规划是什么，动态规划为了解决什么样的问题，怎样用动态规划来解决问题等等。
可以参考知乎上的这篇文章：

什么是动态规划（Dynamic Programming）？动态规划的意义是什么？ - 阮行止的回答 - 知乎

上面这篇回答比较生动形象的描述了动态规划等样貌。
二维数组的本质就是填写一个表格～

那么，我们怎样用动态规划来解决这个最长回文子串问题呢？
我们先考虑一下动态规划中最重要的部分 - 状态转移方程（State Transition Equation）。

我们有了一个二维数组dp，dp[i][j]代表：以下标i为开头，以下标j为结尾的字符串是否是一个回文字符串。
那么显然dp[0][0]，dp[1][1]，dp[2][2]...等等，只包含了1个字符的字符串的情况，当然是回文字符串。

接下来，我们需要考虑2个字符或者3个字符的情况，以下标i为开头，以下标j为结尾的字符串的长度为2或3。
也就是说，当j-i+1 == 2成立时，我们有2个字符，s[i]与s[j]，倘若s[i] == s[j]，那么显然这是一个回文字符串。
并且，当j-i+1 == 3成立时，我们有3个字符，倘若s[i] == s[j]，并且当s[i] == s[j]时，不管中间那个字符是什么，这也是一个回文字符串。
我们就有了第一个状态转移方程：如果j-i+1 <= 2并且s[i] == s[j]，dp[i][j]的值为真。

然后，我们考虑4个字符的情况，以下标i为开头，以下标j为结尾的字符串的长度为4。
也就是说，当j-i+1 == 4时，我们有4个字符了，但是我们这里考虑首尾2个字符，也就是s[i]与s[j]。我们可以得到一个结论，如果s[i] == s[j]，我们需要知道以下标i+1为开头，以下标j-1为结尾的字符串是否是一个回文字符串，我们需要知道dp[i+1][j-1]是否为真。如果它是的，那么显然当s[i] == s[j]时，这4个字符组成的字符串也是一个回文字符串，否则，那么不为一个回文字符串。当然，如果s[i] != s[j]，就不用考虑中间两个字符了，它本来就不是一个回文字符串
我们就有了第二个状态转移方程：如果j-i+1 > 2并且s[i] == s[j]，dp[i][j]的值与dp[i+1][j-1]的值相等。

考虑长度为N的字符串，与长度为4的字符串的情况也是相同的。

归并到一半结论，我们可以构造双重循环，不停地来做填这个表格：

先令dp[0][0]，dp[1][1]，dp[2][2]...dp[n][n]处的值为True，其余为False：
构造双重循环，其中，i为0开始，j为i开始（因为j总是比i大）
- 倘若s[i] == s[j]，并且j-i+1 <= 2，dp[i][j] =True；
- 倘若s[i] == s[j]，并且j-i+1 > 2，dp[i][j] =dp[i+1][j-1]
- 重复以上步骤，令j自增1，直到j > n - 1。
重复以上步骤，令i自增1，直到i > n - 1。

如上面的图所示，我们先填写dp[0][0]，dp[1][1]，dp[2][2]...dp[n][n]处的值为True的情况，然后因为s[i] == s[j]，并且j-i+1 <= 2，于是dp[0][2] = dp[1][1]。
从行列，从小到大填写整张表格，每次填写时记录一下当前的最大值，以及对应的i，j下标即可。

完整的代码在这里。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) == 1:
            return s

        dp = [[0] * len(s) for i in range(len(s))]

        for i in range(len(s)):
            dp[i][i] = 1

        maxLeft = 0
        maxLength = 1

        for j in range(len(s)):
            for i in range(j):

                if s[i] == s[j]:
                    if j - i + 1 <= 3:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i+1][j-1]

                if dp[i][j] == 1:
                    length = j - i + 1

                    if maxLength < length:
                        maxLength = length
                        maxLeft = i

        return s[maxLeft:maxLeft+maxLength]

s = "abcd"
solution = Solution()
print(solution.longestPalindrome(s))

class Solution:

def longestPalindrome(self, s: str) -> str:

if len(s) == 1:

return s

dp = [[0] * len(s) for i in range(len(s))]

for i in range(len(s)):

dp[i][i] = 1

maxLeft = 0

maxLength = 1

for j in range(len(s)):

for i in range(j):

if s[i] == s[j]:

if j - i + 1 <= 3:

dp[i][j] = 1

else:

dp[i][j] = dp[i+1][j-1]

if dp[i][j] == 1:

length = j - i + 1

if maxLength < length:

maxLength = length

maxLeft = i

return s[maxLeft:maxLeft+maxLength]

s = "abcd"

solution = Solution()

print(solution.longestPalindrome(s))

最后

以上就是最长回文子串两个比较简单的解法。
请期待下一篇文章～

经典算法题 – 最长回文子串（Longeset Palindomic Substring）