限制字符串的子串计数

Question

我有一个字符串和一个字典。我需要计算一个给定字符串的子字符串的数量，这些字符串的字母（和字母数量）不超过字典中的数量。我只计算了 15 个子字符串（2a +4b +1d + 2ba + 2ab +bd +db +abc +dba），但我无法编写程序。需要升级（希望只需要ELSE条件）

string = 'babdbabcce'
dict= {'a':1,'b':1,'d':1}
counter= 0
answer = 0

for i in range(len(string)):
    for j in dict:
        if string[i] == j:
            if dict[j] > 0:
                dict[j] = dict[j] - 1
                counter+= 1
                answer+= counter
#             else:                  
print(answer)

Answer 1

您似乎在寻找另一个字符串中的字符串排列（包括其中的子字符串），所以使用字典构建字符串，然后加载排列，然后计算另一个字符串中的排列。请注意，这可能不是最有效的解决方案，但它是有效的。

示例代码：

import itertools
import re

string_to_look_into = 'babdbabcce'
dict= {'a':1,'b':1,'d':1}

permutation_string = ''
for c, n in dict.items():
    permutation_string += c * n


permutations = itertools.permutations(permutation_string)
matches_to_count = set()
for perm in permutations:
    for i in range(1, len(perm)+1):
        matches_to_count.add(''.join(perm[:i]))


sum_dict = {} # to verify matches
sum = 0
for item in matches_to_count:
    count = len(re.findall(item, string_to_look_into))
    sum_dict[item] = count
    sum += count


print(sum)

限制字符串的子串计数

count substrings of a string with limitation

python

string

substring