字谜是回文的子字符串数 [英] number of substring which are whose anagrams are palindrome

问题描述

给出一串数字，计算作为任何回文字母的变位字的子词(一致的子序列)的数量.

Given a string of digits, count the number of subwords (consistent subsequences) that are anagrams of any palindrome.

我在Python中的尝试

My attempt in 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格式

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"

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

It is giving time limit exceeded for big strings. How can I optimize the above code?

我敢肯定，存在比这里更好的解决方案，这就是证明[image] [1]

i bet there exists a better solution than this here is the proof [image][1]

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

推荐答案

此问题有O(n)解决方案.首先要注意的是，如果一个子字符串的回文数包括偶数或至多一个奇数，则它是任何回文字母的拼写形式.例如"20020"是原告的字谜，因为"2"的个数是偶数，"0"的个数是奇数(最多一个奇数)，而"200202"则不正确.

There is an O(n) solution for this problem. The first thing to notice is, a substring is anagram of any palindrome if number of its including digits be even or at most one odd exist. e.g. "20020" is anagram of plaindrome because number of '2's is even and number of '0's is odd(at most one odd) while "200202" is not ok.

因此，我们唯一需要保留的是数字的奇偶校验而不是数字和.我们可以使用10位数字来显示所有数字的奇偶校验.每次访问字符串中的数字时，从0开始，我们可以将奇偶校验数字与(2 ^ digit)进行异或.在您的"02002"示例之后，以下是通过以二进制格式迭代字符串而生成的奇偶校验数字:

So the only thing we need to keep is parity of number of digits not sum of them. we can use a 10-bit number to show the parities of all digits. Starting from 0 each time we visit a digit in string, we can xor the parity number with (2^digit). following your example for "02002" here is the parity numbers generated by iterating through the string in binary format:

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

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

Now we need to count the number of anagrams in linear time. Iterating over the parity_array we use another array of size 1024 (let's call it memo) to keep the number of times we visit a specific number in parity_array. As I mentioned before the substring is ok if and only if the number of 1 bits in their binary parity representation be at most 1. So for each member of parity_array we need to check and add 11 elements in memo having xor with current parity_array value equal to: {0 or 1 or 2 or 4 or 8 ... or 1024} and sum up the results. The total complexity is O(n).

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

I added C++ code for what I explained above. I can also add python code, if you want:

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;

这篇关于字谜是回文的子字符串数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！