讨论/技术交流/求助|不懂就问,同样是O(n)的算法,为什么时间差了10倍?/
求助|不懂就问,同样是O(n)的算法,为什么时间差了10倍?

力扣第五题最长回文子串, 使用Manacher算法,为什么我的代码花了2秒,而官方只花了200ms, 这还是我还稍微优化了一些细节的,不然花了3秒多。

我的代码

class Solution:
    def longestPalindrome(self, s: str) -> str:
        s = '#' + '#'.join(s) + '#'
        n = len(s)
        def expand(i, arm):
            l, r = i - arm - 1, i + arm + 1
            while l >=0 and r <= n - 1 and s[l] == s[r]:
                arm += 1
                l -= 1
                r += 1
            return arm
        arm_len = [0] * n
        max_arm, max_id = 0,0
        j, right = 0, 0
        for i in range(n):
            if i < right:
                arm = min(right - i, arm_len[2 * j - i])
                arm = expand(i, arm)
            else:
                arm = expand(i, 0)
            if i + arm > right:
                j = i
                right = i + arm
            if arm > max_arm:
                max_arm = arm
                max_id = i
        return s[max_id - max_arm + 1: max_id + max_arm: 2]

官方代码


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

    def longestPalindrome(self, s: str) -> str:
        end, start = -1, 0
        s = '#' + '#'.join(list(s)) + '#'
        arm_len = []
        right = -1
        j = -1
        for i in range(len(s)):
            if right >= i:
                i_sym = 2 * j - i
                min_arm_len = min(arm_len[i_sym], right - i)
                cur_arm_len = self.expand(s, i - min_arm_len, i + min_arm_len)
            else:
                cur_arm_len = self.expand(s, i, i)
            arm_len.append(cur_arm_len)
            if i + cur_arm_len > right:
                j = i
                right = i + cur_arm_len
            if 2 * cur_arm_len + 1 > end - start:
                start = i - cur_arm_len
                end = i + cur_arm_len
        return s[start+1:end+1:2]
共 1 个回复

这里 arm_len 数组定义了,但是却没有更新它的值,因此每次都会从 0 开始伸展,就和中心扩展法的复杂度没有区别了。

1