Algorithm to partition a string into substrings in

问题:

The problem:
Let P be the set of all possible ways of partitioning string s into adjacent and possibly null substrings. I'm looking for an elegant algorithm to solve this problem.

Background context:
Given a tuple of strings (s, w), define P(s) and P(w) as above. There exists a particular partition R ∈ P(s) and T ∈ P(w) that yields the least number of substring Levenshtein (insertion, deletion and substitution) edits.

An example:
Partition string "foo" into 5 substrings, where ε is a null substring:

[ε, ε, 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, ε, ε]

回答1:

How about a simple recursive approach?

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

Result:

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