我如何加速这段代码？最长回文子串问题

Question

我正在研究 Leetcode 问题以找到字符串的最长回文子串。这是我的代码。

def longest_palindrome_substring(string):
    
    array = [i for i in string]
    
    # keep track of which substrings are palindromes
    s = [[None for _ in range(len(array))] for _ in range(len(array))]

    # longest substring so far
    best = ""
    
    # look at successively larger substrings
    for substring_length in range(len(array)): # is actually substring length - 1 = stop - start

        # look at the substring from start to stop, inclusive
        for start, stop in zip(range(len(array) - substring_length), [x + substring_length for x in range(len(array) - substring_length)]):
            
            # is it a palindrome?
            if start == stop:
                is_p = True
            elif array[start] == array[stop]:
                if start + 1 == stop:
                    is_p = True
                else:
                    is_p = s[start + 1][stop - 1]
            else:
                is_p = False
            
            # store result
            s[start][stop] = is_p
            
            # is it the best so far?
            if is_p:
                if substring_length + 1 > len(best):
                    best = array[start:stop + 1]

    return "".join(best)

我得到了所有的正确答案，但它说这段代码太慢了。我该怎么做才能加快速度？

我正在尝试关注 strategy outlined here。

Answer 1

解决此问题的最有效方法是使用 Manacher 算法求解复杂度为 O(n) 的解决方案，detailed here。

Python 使用 Manacher 算法的代码：https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-3-2/.

Answer 2

对您的代码进行一些分析，概述如下：

================== PerfTool ==================
task                     |aver(s) |sum(s)  |count   |std     
main loop                |   0.863|   0.863|       1|   0.000
  +-int loop             |   0.001|   0.862|     758|   0.001
    +-is_it_pal?         |   0.000|   0.092|  287661|   0.000
    +-store_res          |   0.000|   0.082|  287661|   0.000
init                     |   0.019|   0.019|       1|   0.000

overall                  |    0.18|    0.88|  576082|-

如您所见，对于一个长 750 个字符的字符串，总共需要 0.9 秒在内部。我的期望是大部分都是零碎的：

 # is it a palindrome?
 # store result
 # is it the best so far?

但事实并非如此，因为他们用了不到 0.2 秒的内部循环 0.8 秒。

所以，主要的时间浪费在这里：

zip(range(len(array) - substring_length), [x + substring_length for x in range(len(array) - substring_length)]):

内部循环的数据准备，耗时0.6s（内部循环的75%）这是整个算法中效率较低的部分。时间花费在创建和销毁大量的子字符串上，所以方向是使用另一种数据结构以避免这种影响。

我如何加速这段代码？最长回文子串问题

How do I speed up this code? longest palindrome substring problem

python

performance

dynamic-programming