string - 将字符串划分为包括空分区的子字符串的算法

Question

问题：
设 P 是将字符串 s 划分为相邻且可能为空的子字符串的所有可能方式的集合。我正在寻找一种优雅的算法来解决这个问题。

背景上下文：
给定一个字符串元组 (s, w)，如上所述定义 P(s) 和 P(w)。存在一个特定的分区 R ∈ P(s) 和 T ∈ P(w) 产生最少数量的子串 Levenshtein（插入、删除和替换）编辑。

示例：将
字符串“foo”划分为 5 个子字符串，其中 ε 为空子字符串：

[ε, ε, f, o, o]  
[ε, f, ε, o, o]  
[ε, f, o, ε, o]  
[ε, f, o, o, ε]

[f, ε, ε, o, o]  
[f, ε, o, ε, o]  
[f, ε, o, o, ε]

[f, o, ε, ε, o]  
[f, o, ε, o, ε]

[f, o, o, ε, ε]

Answer 1

一个简单的递归方法怎么样？

def part(s, n, pre):
    if s == '':
        return [pre + '.' * n]
    elif n > 0:
        res = []
        if n > len(s):
            res += part(s, n-1, pre + '.')
        if len(s) > 0:
            res += part(s[1:], n-1, pre + s[0])
        return res

结果：

>>> print part('foo', 5, '')
['foo..', 'fo.o.', 'fo..o', 'f.oo.', 'f.o.o', 'f..oo', '.foo.', '.fo.o', '.f.oo', '..foo']