想法
让您要交错的两个字符串为
s和
t。我们将使用递归生成所有可能的方式来交织这两个字符串。
如果在任何时间点我们已经对的第一个
i字符
s和的第一个
j字符进行
t了交织以创建某个字符串
res，那么我们可以通过两种方式对它们进行交织以进行下一步：
- 追加
i+1
的个字符s
来res
- 追加
j+1
的个字符t
来res
我们继续进行递归，直到使用了两个字符串的所有字符，然后将结果存储在字符串列表中，
lis如下面的代码所示。
编码
def interleave(s, t, res, i, j, lis): if i == len(s) and j == len(t): lis.append(res) return if i < len(s): interleave(s, t, res + s[i], i + 1, j, lis) if j < len(t): interleave(s, t, res + t[j], i, j + 1, lis)l = []s = "ab"t = "cd"interleave(s, t, "", 0, 0, l)print l
输出量
['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']
由于我们从未两次生成相同的字符串，因此这种实现方式（至少渐近地）是高效的。
