null 파티션을 포함한 하위 문자열로 문자열을 분할하는 알고리즘

Question

문제 :
문자열을 인접한 null 문자열로 분할하는 가능한 모든 방법을 P라고 가정합니다. 나는이 문제를 해결하기위한 우아한 알고리즘을 찾고있다.

배경 컨텍스트 :
문자열 (s, w)의 튜플이 주어지면, 위와 같이 P (s)와 P (w)를 정의하십시오. 부분 문자열 Levenshtein (삽입, 삭제 및 대체) 편집 수가 가장 적은 특정 파티션 R ∈ P (s)와 T ∈ P (w)가 있습니다.

예 :
파티션 문자열 5 개 문자열에 "foo는"ε는 널 (null) 문자열입니다 : 어떻게 간단한 재귀 적 접근 방법에 대한

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