string - 生成字符串的所有覆盖子字符串

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

Answer 2

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 3

要获得特定的拆分：

• 首先，决定在哪些索引处进行拆分；
• 然后，在给定的索引处拆分字符串。

对于长度为 的字符串n，给定的一组拆分索引是 of 的一个powerset元素{1, ..., n}。

在蟒蛇中：

from itertools import combinations, chain

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def pairs(seq, end):
    "pairs([13,23,33], 55) --> (0,13) (13,23) (23,33) (33,55)"
    return zip(chain((0,), seq), chain(seq, (end,)))

def allsplits(s):
    "allsplits('abc') --> ['abc'] ['a', 'bc'] ['ab', 'c'] ['a', 'b', 'c']"
    for split_indices in powerset(range(1,len(s))):
        yield [s[i:j] for i,j in pairs(split_indices, len(s))]

print(list( allsplits('abcd') ))
# [['abcd'], ['a', 'bcd'], ['ab', 'cd'], ['abc', 'd'], ['a', 'b', 'cd'], ['a', 'bc', 'd'], ['ab', 'c', 'd'], ['a', 'b', 'c', 'd']]