Suppression de doublons consécutifs

Exercice difficile

Écrire une fonction récursive nettoie qui renvoie une copie de son paramètre texte où l'on a supprimé deux caractères consécutifs identiques, en répétant l'action si nécessaire.

Exemple

🐍 Console Python

>>> nettoie('bbcdaadz')
'cz'

En effet :

• on peut supprimer 'bb', ce qui donne 'cdaadz'
• on peut supprimer 'aa', ce qui donne 'cddz'
• on peut supprimer 'dd', ce qui donne 'cz'

Quel que soit l'ordre de suppression des doublons, on arrive à 'cz'

Indices

Il faudrait envisager trois cas distincts :

1. le texte fait moins de deux caractères,
2. le texte commence par deux caractères identiques,
3. le texte commence par deux caractères différents.

Pensez à ajouter une docstring et de nombreux tests unitaires !

###

LancerTéléchargerTéléverser RechargerSauvegarder

Réponse

🐍 Script Python

def nettoie(texte):
    """Renvoie le texte nettoyé suivant la règle donnée"""
    if len(texte) < 2:
        return texte
    elif texte[0] == texte[1]:
        return nettoie(texte[2:])
    else:
        # Il y a deux caractères distincts au début
        suite = nettoie(texte[1:])
        if len(suite) > 0 and texte[0] == suite[0]:
            return suite[1:]
        else:
            return texte[0] + suite

• Analysez tranquillement cette solution, plusieurs fois !!!
• Attardons-nous ensuite sur la ligne suivante :
  • if len(suite) > 0 and texte[0] == suite[0]:
  • il y a une évaluation paresseuse du and,
  • si len(suite) > 0 est faux, la suite du and n'est pas testée (c'est inutile), et aucune erreur n'est provoquée avec suite[0] (pourtant suite est vide) !!!
• Analysez encore cette solution !!!