Re: Problème 3

Ma solution est de ne travailler qu'en morse, et récursivement pour n de 1 à la taille L du texte (taille en morse). Pour tout n, nbr[n] est le nombre de possibilités pour faire un texte de taille n du texte. On fixe nbr[0]=1, puis on trouve nbr[n]=somme(nbr[j], j=n-M…n-1), avec M la taille maximale que peut faire un mot, écrit en morse.

La complexité est en O(M*L*log(N)), avec N le nombre de mots dans le dictionnaire. Il faut tester l'existence d'un mot en utilisant des ensembles, pour avoir un test efficace en log(N).

Mon code:

import sys
morse = { 'A': '.-', 'B': '-...', 'C': '-.-.', 'D': '-..', 'E': '.', 'F': '..-.', 'G': '--.', 'H': '....', 'I': '..', 'J': '.---', 'K': '-.-', 'L': '.-..', 'M': '--', 'N': '-.', 'O': '---', 'P': '.--.', 'Q': '--.-', 'R': '.-.', 'S': '...', 'T': '-', 'U': '..-', 'V': '...-', 'W': '.--', 'X': '-..-', 'Y': '-.--', 'Z': '--..',
}
l = sys.stdin.readline()[:-1]
n = int(sys.stdin.readline()[:-1])
words = []
for _ in xrange(n):
 words.append(sys.stdin.readline()[:-1])
mwords = ["".join(morse[c] for c in w) for w in words]
M=max(len(mw) for mw in mwords)
smwords = set(mwords)
nbr = [0 for _ in xrange(len(l)+1)]
nbr[0] = 1
for i in xrange(1,len(nbr)):
 for j in xrange(i-M,i-1):
 if j>=0 and l[j: i] in smwords: 
 nbr[i] += nbr[j]
print nbr[-1]