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

Question

我正在尝试生成所有可能的方法来从 Python 中的源字符串构建目标字符串。

来源：猫猫
目标：猫

输出：5

(猫)猫
(ca)t(t)猫
(ca)ttca(t)
(c)attc(at)
猫（猫）

Answer 1

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

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')]]

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

Answer 2

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 3

您可以使用 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)]

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

find all possible ways to build a specific string

python

permutation