这两种解决方案的时间复杂性是什么？

Question

我正在解决这个问题：回文子串

给定一个字符串，您的任务是计算该字符串中有多少回文子字符串。

具有不同开始索引或结束索引的子字符串被计为不同的子字符串，即使它们包含相同的字符。

我尝试了多种方法，根据我的说法，这两种方法的复杂性都为O（N*3）。但是leetcode接受一种解决方案并返回超过另一种解决方案的时间限制。

可接受的解决方案：

def countSubstrings(self, s):
        count = len(s)
        for i in range(2, len(s)+1):
            j = 0
            while(j < len(s) and j+i <= len(s)):
                t = s[j:j+i]
                j = j + 1
                reverse_t = t[::-1]
                if t == reverse_t:
                    count += 1
        return count

超出时间限制的解决方案

def countSubstrings(self, s):
        count = len(s)
        for i in range(2, len(s)+1):
            j = 0
            while(j < len(s) and j+i <= len(s)):
                t = s[j:j+i]
                j = j + 1
                reverse_t = ''
                for k in range(len(t)-1, -1, -1):
                    reverse_t += t[k]
                if t == reverse_t:
                    count += 1
        return count

这两种算法中唯一的变化是，第一种算法使用Python切片来反转字符串，第二种算法使用for循环。切片的时间复杂度是O（K），其中K是切片的长度

Answer 1

您写道：

reverse_t = ''
for k in range(len(t)-1, -1, -1):
    reverse_t += t[k]

因为字符串是不可变的，所以通过一次添加1个字母来构造字符串效率非常低，因为在每次迭代中，您都必须构造一个全新的对象。本质上，这是您在计算中没有考虑到的字符串连接。逐个字母构造长度为n的字符串实际上是o（n**2）

为了展示这能带来多大的不同，这里有一个简单的设置：

def letter_by_letter_reverse(string):
    reverse_t = ''
    for k in range(len(string)-1, -1, -1):
        reverse_t += string[k]
    return reverse_t

def slice_reverse(string):
    reverse_t = string[::-1]
    return reverse_t

test = 'some_string' * 500

%timeit letter_by_letter_reverse(test)
#1.44 ms ± 204 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit slice_reverse(test)
#8.2 µs ± 56.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)