给定一个仅由0、1或2s组成的字符串，计算0、1和2s数目相等的子串的数目

Question

我正在学习算法/数据结构。为了提高我的知识，我试图解决一些网上的问题。 我要解决的一个问题是在practiceque给出的

我试过以下方法：

def count_zero_one_two():
    s = '102100211'
    s_len = len(s)
    count = 0
    for i in range (s_len-1):
        j = i+1
        k = j+1
        #print i, j, k, count
        #print s[i], s[j], s[k]
        if k > (s_len-1):
            print "end"
            break

        elif (s[i] != s[j]) and (s[i] !=s[k]) and (s[j] != s[k]):
            print s[i], s[j], s[k]
            print "not equal"
            count = count+1
            #print count
        else:
            print s[i], s[j], s[k]
            print "equal"
        k = j +i
    print count


count_zero_one_two()

问题：如果我的输入字符串是“102100211”，那么count应该是5，但我得到的是4。有什么想法吗？

Answer 1

from collections import Counter

def countSub(s):
    result = []

    for i in range(3, len(s), 3):
        t = s[:i]
        c = list(Counter(t).values())
        if (c[0]==c[1]==c[2]):
            result.append((t, c[0]))

    return result


def count(s):
    result = []
    for i in range(len(s)-2):
        result.extend(countSub(s[i:]))

    return set(result)




ss = count("102100211")    
print("%s substrings found: " % len(ss), ss)    

输出：

^{pr2}$

Answer 2

我会这样解决：

def count_zero_one_two(s):
    num = 0
    for i in range(len(s)):
        for j in range(1, len(s)/3 + 1):
            if all(s[i:i+3*j].count(n) == j for n in '012'):
                num += 1
    return num

^{}用于检查所有3个字符（对于每个迭代）是否都在“012”中。在

内部for循环用于按长度3、6、9等顺序计算0、1和2的数目

输出：

^{pr2}$