Vérifier si une chaîne peut être créée en liant des éléments dans une liste

Question

Je veux vérifier si une chaîne peut être créée en liant des éléments dans une liste donnée, et quelle est cette concaténation. Par exemple:

String = 'BIBER' 
List = ['BI', 'BIB', 'BIBE', 'BE', 'BER', 'ER'] 

'BIBER' peut être construit à partir de 'BI' et 'BER',

pour que le programme doit retourner TRUE et une liste des composants:

components = ['BI','BER'] 

J'ai déjà essayé, mais je ne peux pas vérifier ce que les composants sont:

r = re.compile("(?:" + "|".join(List) + ")*$") 
    if r.match(Word) != None: 
     print('TRUE') 

Answer 1

Vous pouvez juste d o force brute:

s = 'BIBER' 
li = ['BI', 'BIB', 'BIBE', 'BE', 'BER', 'ER'] 

import itertools as it 

for i in range(2,len(li)+1): 
    for t in it.permutations(li, i): 
     if ''.join(t)==s: 
      print t 

Prints:

('BI', 'BER') 
('BIB', 'ER') 

Si vous voulez vérifier si un certain groupe de chaînes sous peut être complètement combiné pour égaler une chaîne:

def builds(s, componts): 
    return any(s==''.join(t) for t in it.permutations(componts)) 

>>> builds(s, ('R','BE','I','B')) 
True 

Cela ne gérer la réutilisation de différentes sous-chaînes plus d'une fois (comme ('B','I','E','R')) Pour cela, vous pourriez envisager d'utiliser un Trie.

Answer 2

En utilisant itertools.combinations ...

Cette fonction devrait faire le travail:

def check(String, List): 
    return String in [a+b for a,b in itertools.combinations(List, 2)] 

qui retourne True pour votre entrée:

check('BIBER', ['BI', 'BIB', 'BIBE', 'BE', 'BER', 'ER'])