Longest Palindromic Substring

Longest Palindromic Substring

描述

给定一个字符串, 找出最长的对称的子串

示例:
输入: "abbaad"
输出: "bbaa"

分析

我们先来求最长的对称子串长度

从开头开始遍历字符串, 从每个字符的左右延伸, 判断最长的对称字符串长度, 取最大值, 复杂度是\(O(n^2)\)

需要注意的是, 在对称字符串中, 对称字符不一定存在于字符串中, 对于偶数长度的对称字符串, 对称中心是中间的位置, 所以我们处理一下字符串, 用#将所有字符分割, 然后遍历处理即可, 代码如下

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        t = ""
        for i in s:
            t += i + "#"
        t = t[0:-1]

        cnt = 0
        max_cnt = 0

        for i in range(len(t)):
            cnt = 1
            for j in range(1, i + 1):
                cnt = j
                s = i - j
                e = i + j
                if s < 0 or e >= len(t):
                    break
                if t[s] != t[e]:
                    break

            if cnt + 1 > max_cnt:
                max_cnt = cnt + 1
        return max_cnt

求最长的子串, 只需要记录最长值的时候顺便记一下下标即可, 由于加入#的时候, #的位置都是奇数位, 最后组装字符串时跳过奇数位即可

然而, 这种复杂度的解法提交超时

稍微思考一下, 在一个对称的字符串中, 左右的对称性不只表现在字符相同, 还表现在对称字符的对称字符串长度也是相同的, 如下字符串所示:

    [a # a # c # d # d # c # a # a]
    [1 2 2 1 2 1 2 8 2 1 2 1 2 2 1]

以最长的8为中心, 左右两侧的对称字符, 以他们为中心的最长的对称字符串长度也是相等的, 因此, 利用这个特性, 可以减少一些计算量

在更长的字符串中, 根据这种对称算法得出来的值不一定是最终值, 如果按照对称值, 字符串向右延伸的部分超过了参考的对称字符串的边界, 就不能再使用对称值, 需要选择对称值与右边界减去当前下标的最小值, 接下来需要按照传统的方法逐个判断是否对称, 之后更新参考字符串的位置即可

一个可以过 OJ 的答案如下:

答案

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """

        t = "#"
        for i in s:
            t += i + "#"

        p = {0:0} # p[i] used to store the longest string len with i as the center
        c = 0 # center index
        r = 1 # the right side of the string used c as the center
        max_len_i = 0

        for i in range(len(t)):
            im = c + (c - i)
            if im < 0:
                p[i] = 0
            else:
                if i + p[im] > r:
                    p[i] = r - i
                else:
                    p[i] = p[im]

            while True:
                left = i - p[i]
                right = i + p[i]
                if left < 0 or right >= len(t):
                    break
                if t[left] != t[right]:
                    break
                p[i] += 1
            if i + p[i] > r:
                c = i
                r = i + p[i]
            if p[i] > p[max_len_i]:
                max_len_i = i

        start = max_len_i - (p[max_len_i] - 1)
        end = max_len_i + (p[max_len_i] - 1)
        return s[start/2:end/2]
打赏