Bonjour,
J’ai essayé de faire la question Decode Ways sur leetcode et j’ai remarqué que mon code est à peu près similaire à un autre mais la complexité est bien différente.
La question est de trouver toutes les manières possibles pour décoder une chaîne (de caractères) d’entiers sachant que les entiers sont associés à des lettres selon la règle suivante : 'A' est associée à 1, 'B' à 2, …, 'Z' à 26. Une chaîne de caractères du genre '02' ne peut pas être décodée et de même pour '0’. Si la chaîne de caractères est '12' alors il y a deux manières de la décoder: (1 1) qui correspond à 'AA' ou (12) qui correspond à 'L’. Par contre il n’y a qu’une seule manière de décoder '10' et qui est 'J’. Il n’y a aucune manière de décoder '1405' par contre, car (1 40 5) est invalide puisqu’on peut pas décoder 40, de même (14 0 5) à cause du 0 et (1 4 05) à cause du 05.
Mon code est le suivant:
class Solution:
@cache
def numDecodings(self, s: str) -> int:
if (len(s) == 0) or (len(s) == 1 and s != '0'):
return 1
return (self.numDecodings(s[1:]) if s[0] != '0' else 0) + \
(self.numDecodings(s[2:]) if s[0] != '0' and 1 <= int(s[:2]) <= 26 else 0)
Sur les tests de leetcode ce code dure 35 ms et utilise 14.8 MB de mémoire.
Le meilleur code que j’ai trouvé dans les solutions est:
class Solution:
def numDecodings(self, s: str) -> int:
@cache
def dp(i):
if i>=len(s):return 1
return (dp(i+2) if i!=len(s)-1 and s[i]!='0' and 0<int(s[i]+s[i+1])<=26 else 0)+(dp(i+1) if s[i]!='0' else 0)
return dp(0)
Je ne sais pas si ce code a été soumis aux mêmes tests (je suppose que oui) mais il dure 32 ms et utilise 14.5 MB.
En cherchant s’il y a une différence entre ces deux codes je ne vois pas trop la différence. Peut-être que j’ai un test de plus que lui avec mon or mais c’est tout.
J’espère que vous pourrez m’aider à comprendre comment analyser et comparer ces codes.
Merci d’avance.
