最长回文字符串(Leetcode 5)

题目分析

   最长回文子串问题是一个经典的字符串处理问题，这道题有四种不同的解决思路，当然它们的时间复杂度和空间复杂度也都不相同。

暴力法

暴力法很好理解，遍历所有子串，需要$O(n^2)$的时间复杂度，每个子串比较是否为回文串，需要O(n)的时间复杂度，因此总的时间复杂度为$O(n^3)$，空间复杂度上，如果使用一个临时变量存储子串则需要O(n)，如果直接使用索引则空间复杂度为O(1)，使用临时变量思路更加清晰，在这里我就使用O(n)的空间复杂度。

class Solution:
    def longestPalindrome(self, s):
        """
        :s: str
        :rtype: str
        """
        lens = len(s)
        if lens == 0:
            return ''
        for i in range(lens, 0, -1):
            for j in range(lens - i + 1):
                tmp = s[j:j + i]
                for k in range(i // 2):
                    if tmp[k] != tmp[-k - 1]:
                        break
                else:
                    return tmp

DP

DP是(Dynamic Programming，动态规划)的简称，动态规划的核心问题是如何建立状态转移方程，而本题有一个天然的状态，即回文状态，如果某个字符串是回文字符串，那么去掉首尾的一个字符，仍然满足回文字符串，因此可以容易的建立状态转移方程，其时间复杂度为$O(n^2)$，空间复杂度也是$O(n^2)$。

有关DP的知识可以参考我的另一篇博客动态规划(Dynamic Programming)。

class Solution:
    def longestPalindrome(self, s):
        """
        :s: str
        :rtype: str
        """
        lens = len(s)
        if lens == 0:
            return ''
        result = s[0]
        dp = [[True if col <= row else False for col in range(lens)] for row in range(lens)]
        for length in range(2, lens + 1):
            for j in range(lens - length + 1):
                dp[j][j + length - 1] = dp[j + 1][j + length - 2] and (s[j] == s[j + length - 1])
                if dp[j][j + length - 1] and length > len(result):
                    result = s[j:j + length]
        return result

中心扩展算法

中心扩展算法不是一类通用算法，是针对于特定回文字符串的问题的解法，分析如下图，时间复杂度为$O(n^2)$，如果采用一个临时变量存储子串则需要O(n)，如果直接使用索引则空间复杂度为O(1)，使用临时变量思路更加清晰，在这里我就使用O(n)的空间复杂度。

class Solution:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

manacher(马拉车)算法

马拉车算法是专门解决回文字符串的问题，其算法的时间复杂度和空间复杂度都可以缩小到O(n)的量级，在长字符串中具有非常显著的优势。

class Solution:
    def longestPalindrome(self, s):
        """
        :s: str
        :rtype: str
        """
        new_s = '#'
        for i in s:
            new_s += (i + '#')
        C, p1, R = 0, 0, 0
        len_ns = len(new_s)
        radius = [1] * len_ns
        while R < len_ns - 1:
            p1 += 1
            if p1 > R:
                C = p1
                R += 1
                while 2 * C - (R + 1) >= 0 and R + 1 < len_ns and new_s[R + 1] == new_s[2 * C - (R + 1)]:
                    R += 1
                radius[C] = R - C + 1
            else:
                p2 = 2 * C - p1
                pL = p2 - radius[p2] + 1
                CL = C - radius[C] + 1
                if CL < pL:
                    radius[p1] = radius[p2]
                elif CL > pL:
                    radius[p1] = R - p1 + 1
                else:
                    C = p1
                    while 2 * C - (R + 1) >= 0 and R + 1 < len_ns and new_s[R + 1] == new_s[2 * C - (R + 1)]:
                        R += 1
                    radius[C] = R - C + 1
        longest = max(radius)
        index = radius.index(longest)
        begin_index, end_index = index - longest + 1, index + longest - 1
        return new_s[begin_index:end_index + 1:2] if new_s[begin_index] != '#' else new_s[begin_index + 1:end_index + 1:2]

刷题总结

  马拉车算法是解决最长回文串的最佳方法，在面试中问到回文串，如果能答出马拉车算法，那是非常给力的，但是动态规划的方法大家也要学会，因为动态规划问题也是面试常考的知识点之一。