將字符串劃分爲包含空分區的子字符串的算法

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