找到所有可能的方法来构建特定字符串

Question

我试图用Python中的源字符串生成所有可能的方法来构建目标字符串

• 资料来源：卡特尔猫
• 目标：猫

产出：5

• （cat）tcat
• （ca）t（t）cat
• （ca）ttca（t）
• （c） attc（at）
• 猫

Answer 1

Simple String , array and Dictionary 
    s = "cattcat"
    t = "cat"
    n = len(s)
    nt = len(t)
    a={}
    for i  in range(0,nt):
        c = t[i]
        for j in range(0,n):
            if (s[j] == c):
                if c in a:
                    try:
                        a[c].append(j+1)
                    except:
                        a[c]=[a[c],j+1]
                else:
                    a[c]=j+1
    print(a)
    for z in range(0,len(a['c'])):
        for y in range(0,len(a['a'])):
            for x in range(0,len(a['t'])):
                if(a['c'][z]<=a['a'][y]<=a['t'][x]):
                    print(a['c'][z],a['a'][y],a['t'][x])

Answer 2

您可以使用itertools.combinations获得所有可能组合的列表。使用zip，您不仅可以跟踪角色，还可以跟踪角色的位置。整个过程变成一个单一的列表理解练习，应该是相当有效的

from itertools import combinations
src='cattcat'
trg='cat'

comb_lst=[idx for el, idx in zip(
combinations(src,len(trg)),
combinations(range(len(src)),len(trg))
) if ''.join(el)==trg]

print(comb_lst)

输出：

[(0, 1, 2), (0, 1, 3), (0, 1, 6), (0, 5, 6), (4, 5, 6)]

Answer 3

可以使用递归生成器函数：

def get_combos(d, s, i = 0, c = []):
   if (r:=''.join(b for _, b in c)) == s:
      yield c
   elif d:
     if s.startswith(r+d[0]):
        yield from get_combos(d[1:], s, i = i+1, c=c+[(i, d[0])])
     yield from get_combos(d[1:], s, i = i+1, c=c)

print(list(get_combos('cattcat', 'cat')))

输出：

[[(0, 'c'), (1, 'a'), (2, 't')], 
 [(0, 'c'), (1, 'a'), (3, 't')], 
 [(0, 'c'), (1, 'a'), (6, 't')], 
 [(0, 'c'), (5, 'a'), (6, 't')], 
 [(4, 'c'), (5, 'a'), (6, 't')]]

出于演示的目的，原始源字符串中每个字符的索引都包含在输出中