如何从给定字符串中查找以特定字符 say 'a' 开头并以特定字符 say 'b'
结尾的字符串的可能子序列总数?
例子:
对于字符串 'aabb'
如果我们想知道有多少个子序列是可能的 如果子序列必须从字符 'a'
开始并以字符结束'b'
那么有效的子序列可以来自 (ab)
由索引贡献 (0,2), (ab)
由索引 (0,3), (ab)
由索引 (1,2), (ab)
由索引 (1,3), (aab)
使用索引 (0,1,2) , (aab)
使用索引 (0,1,3) ,(abb)
使用索引(0 ,2,3),(abb)
使用索引(1,2,3)
和 aabb
本身
所以总数是 9。我可以解决一个小长度的字符串,但是如何解决一个大字符串的问题,其中蛮力不起作用
Note:We consider two sub strings to be different if they start or end at different indices of the given string.
def count(str,str1 ,str2 ):
l = len(str)
count=0
for i in range(0, l+1):
for j in range(i+1, l+1):
if str[i] == str1 and str[j-1] == str2:
count+=1
return count
最佳答案
在发布我的主要代码之前,我将尝试解释它是如何工作的。让源字符串为“a123b”。有效子序列由“123”的所有子集组成,前缀为“a”,后缀为“b”。所有子集的集合称为 powerset ,itertools
文档中的代码展示了如何使用 combinations
在 Itertools Recipes 中生成幂集。部分。
# Print all subsequences of '123', prefixed with 'a' and suffixed with 'b'
from itertools import combinations
src = '123'
for i in range(len(src) + 1):
for s in combinations(src, i):
print('a' + ''.join(s) + 'b')
输出
ab
a1b
a2b
a3b
a12b
a13b
a23b
a123b
这是一个使用该配方的蛮力解决方案。
from itertools import combinations
def count_bruteforce(src, targets):
c0, c1 = targets
count = 0
for i in range(2, len(src) + 1):
for t in combinations(src, i):
if t[0] == c0 and t[-1] == c1:
count += 1
return count
很容易证明the number of subsets of a set of n
items is 2**n
.因此,与其一个一个地生成子集,我们还可以使用该公式来加快该过程,这就是我的 count_fast
函数所做的。
from itertools import combinations
def count_bruteforce(src, targets):
c0, c1 = targets
count = 0
for i in range(2, len(src) + 1):
for t in combinations(src, i):
if t[0] == c0 and t[-1] == c1:
count += 1
return count
def count_fast(src, targets):
c0, c1 = targets
# Find indices of the target chars
idx = {c: [] for c in targets}
for i, c in enumerate(src):
if c in targets:
idx[c].append(i)
idx0, idx1 = idx[c0], idx[c1]
count = 0
for u in idx0:
for v in idx1:
if v < u:
continue
# Calculate the number of valid subsequences
# which start at u+1 and end at v-1.
n = v - u - 1
count += 2 ** n
return count
# Test
funcs = (
count_bruteforce,
count_fast,
)
targets = 'ab'
data = (
'ab', 'aabb', 'a123b', 'aacbb', 'aabbb',
'zababcaabb', 'aabbaaabbb',
)
for src in data:
print(src)
for f in funcs:
print(f.__name__, f(src, targets))
print()
输出
ab
count_bruteforce 1
count_fast 1
aabb
count_bruteforce 9
count_fast 9
a123b
count_bruteforce 8
count_fast 8
aacbb
count_bruteforce 18
count_fast 18
aabbb
count_bruteforce 21
count_fast 21
zababcaabb
count_bruteforce 255
count_fast 255
aabbaaabbb
count_bruteforce 730
count_fast 730
可能有一种方法可以通过在正确的位置启动内部循环而不是使用continue
来跳过不需要的索引来加快速度。
关于python - 如何找到字符串的可能组合总数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46988489/