Un palindrome est une séquence qui est indépendante du sens de lecture, c'est-à-dire une séquence qui est identique qu'elle soit lue de gauche à droite ou de droite à gauche. Par exemple, les mots radar et kayak sont des palindromes, le mot bonbon n'en est pas un.
Vous êtes chargés d'implémenter les fonctions is_palindrome_rec
et is_palindrome
étant donné les propriétés suivantes :
- Une séquence contenant aucun caractère peut être considérée comme un palindrome.
- Une séquence contenant exactement un caractère est un palindrome.
- Une séquence est un palindrome si le premier et dernier caractère sont identiques, que le deuxième et avant-dernier caractère sont identiques, ...
Vous noterez que les chaînes de caractères Python (str
) peuvent être vues comme des tableaux immuables.
Cela signifie :
que vous pouvez utiliser les
str
comme des tableaux (list) mais que, comme les tuples en Python, vous ne pouvez pas modifier leur contenusupposons que
s = "hello"
alorss[:2]
renvoie"he"
,s[1]
renvoie"e"
ets[2:]
renvoie"llo"
lorsque, comme ci-dessus, on extrait une sous-chaîne d'une chaîne
s
de longueur n, cette extraction se réalise en réalité en recopiant les caractères concernés dans une nouvelle chaîne.Par conséquent,
- accéder à
s[:2]
s'exécute en temps constant Θ(1) car on n'a qu'un nombre constant de caractères (ici les2
premiers) à recopier, quelle que soit la longueur totale n de la chaînes
. - accéder à
s[2:]
s'exécute en O(n) car on doit recopier n−2 caractères de la chaînes
, donc tous sauf les2
premiers.
- accéder à