python - 其字谜是回文的子串的数量

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

输入/输出格式

For example, given:

    S = "02002"
the function should return 11. 
these are 11 substrings whose anagrams are palindrome
"0", "2", "0", "0", "2", "00", "020", "200", "002", "2002", "02002"

它给出了超过大字符串的时间限制。如何优化上面的代码？

我打赌有比这更好的解决方案，这就是证据[图片][1]

/image/7x3Jq.png

Answer 1

这个问题有一个 O(n) 的解决方案。首先要注意的是，一个子串是任何回文的变位词，如果它包含的数字的个数是偶数或最多存在一个奇数。例如"20020"是 plaindrome 的变位词，因为 '2' 的个数是偶数，'0' 的个数是奇数(最多一个奇数)，而 "200202"则不行。

所以我们唯一需要保留的是位数的奇偶校验而不是它们的总和。我们可以用一个 10 位的数字来表示所有数字的奇偶性。每次我们访问字符串中的数字时都从 0 开始，我们可以用 (2^digit) 异或奇偶校验数。按照您的“02002”示例，这里是通过以二进制格式迭代字符串生成的奇偶校验数:

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

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

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

string sample = "02002";
int parity = 0;
vector<int> parity_array;
parity_array.push_back(parity);
for(int i=0; i<sample.size(); ++i){
    parity ^= 1<<(sample[i]-'0');
    parity_array.push_back(parity);
}
int memo[1025] = {0};
int res=0;
for(int i=0;i<parity_array.size();++i){
    for(int j=-1;j<10;++j)
        res += memo[(1<<j)^parity_array[i]];
    memo[parity_array[i]]++;
}
cout<<res<<endl;