将字符串分解为已知模式

Question

这是字符串的python列表:

patterns = ["KBKKB","BBBK","BKB","KBBB","KBB","BKBB","BBKB","KKBKB","BKBK","KBKB","KBKBK","BBK" ,"BB","BKKB","BBB","KBBK","BKKBK","KB","KBKBK","KKBKKB","KBK","BBKBK","BBBB","BK"," KKBKBK","KBBKB","BBKKB","KKKKBB","KKB"]

我有一个输入字符串,由K和B组成,只有任意长度.我想知道输入字符串的所有可能的完整分解.只是一个8 B串的例子:

BBBBBBBB

这里有可能的分解

BB BB BB BB BB

BBBB BBBB

BBBB BB BB

BB BB BBBB

BBB BBB BB

BB BBB BBB

任何人都可以指导我如何去做吗？我现在不太关心效率.

Answer 1

这是使用递归的一种方法:

def getPossibleDecompositions(s):
    if s == '':
        yield []
    else:
        for pattern in patterns:
            if s.startswith(pattern):
                for x in getPossibleDecompositions(s[len(pattern):]):
                    yield [pattern] + x

for x in getPossibleDecompositions('BBBBBBBB'):
    print x