其换位符为回文的子串数

Question

给定一个数字串，计算任何回文的转写字的子字（一致的子序列）的数量。在

我在Python中的尝试：

def ispalin(s):
    if len(s)%2==0:
        for i in s:
            if s.count(i)%2!=0:
                return False
    else:
        sum =0
        for i in set(s):
            if s.count(i)%2==1:
                sum = sum+1
        if sum == 1:
            return True
        else:
            return False

    return True

def solution(S):
    # write your code in Python 3.6
    count=len(S)
    for i in range(len(S)):
        for j in range(i+1,len(S)):
            if ispalin(S[i:j+1]):
                count=count+1

    return count

i/o格式

^{pr2}$

它给出了超过大弦的时间限制。如何优化上述代码？在

我敢打赌有比这更好的解决办法这里就是证据 [图像][1]

https://i.stack.imgur.com/7x3Jq.png

Answer 1

这个问题有一个O（n）的解决方案。首先要注意的是，如果子串包含的数字是偶数或最多有一个奇数，则子串就是任何回文的变音图。e、 g.“20020”是plaindrome的换位符，因为“2”的数目是偶数，“0”的数目是奇数（最多是一个奇数），而“200202”是不正常的。在

所以我们只需要保持位数的奇偶性，而不是它们的和。我们可以用一个10位数字来表示所有数字的平价。从0开始，每次访问字符串中的一个数字，我们可以用（2^位）对奇偶校验数进行异或运算。下面是“02002”的示例，通过迭代二进制格式的字符串生成奇偶校验数：

parity_array = {0000000000, 0000000001, 0000000101, 0000000100, 0000000101 0000000001}

现在我们需要计算线性时间内的字谜数。在奇偶校验数组上迭代时，我们使用另一个1024大小的数组（我们称之为memo）来保持奇偶校验数组中特定数字的访问次数。正如我前面提到的，当且仅当二进制奇偶校验表示中的1位的数目最多为1时，子串是可以的。因此，对于奇偶校验数组的每个成员，我们需要检查并在memo中添加11个元素，当前奇偶校验数组的值等于：{0、1、2、4或8。。。或1024}并总结结果。 总复杂度为O（n）。在

编辑： 我为上面所解释的添加了C++代码。如果您需要，我还可以添加python代码：

^{pr2}$

Answer 2

你可以得到二次复杂度使用O（n）的内存。在

使数字计数器数组[0..9]（或使用其他便于Python使用的数据结构）

遍历字符串，为当前数字递增计数器，并将修改后的数组添加到列表中。之后的列表将包含“累计和”-每个数字的计数，直到每个索引（例如，在第40个字符串条目之前有5个2）

现在要计算第i个和第j个条目之间的位数，只需减去C[j][digit] - C[i][digit]

有趣的问题-是否存在更好的复杂性解决方案？在