生成一個字符串的所有覆蓋子字符串

Question

你如何做到以下幾點：給定一個字符串，生成所有可能的方法來將該字符串解析爲子字符串（時間很重要，空間不要在意）。 例如，給定的字符串ABCD，我需要生成：

ABCD 

A BCD 

A BC D 

A B CD 

AB CD 

AB C D 

ABC D 

A B C D 

可能是一個遞歸解決方案，但我不能完全得到它的工作。

Answer 1

的Python：

def splitstring(s): 
    result = [s] 
    for i in range(1, len(s)): 
    result.extend('%s %s' % (s[:i], x) for x in splitstring(s[i:])) 
    return result 

Answer 2

在Python另一種解決方案，且無需遞歸：

def substrings(s): 
    for k in xrange(1, len(s)+1): 
     for i in xrange(len(s)-k+1): 
      yield s[i:i+k] 

使

>>> print list(substrings("ABCD")) 
['A', 'B', 'C', 'D', 'AB', 'BC', 'CD', 'ABC', 'BCD', 'ABCD']