Aller au contenu

Anagrammes⚓︎

Deux chaines de caractères de même longueur sont des anagrammes s'il est possible d'écrire l'une en utilisant tous les caractères de l'autre, quitte à les déplacer.

Par exemple les chaines chien et niche sont des anagrammes, alors que louve et poule ne le sont pas.

Déterminer si deux chaines de caractères sont des anagrammes peut se faire en les comparant après les avoir triées.

On utilise ici une autre approche, récursive :

  • si les deux chaines sont de longueur 1, on renvoie True ou False selon qu'elles sont égales ou non
  • sinon, on teste si le premier caractère de la première se trouve aussi dans la seconde :
    • si oui, on recommence le test sur les deux chaines dans lesquelles on a retiré la première apparition du caractère testé
    • si non, on renvoie False

Exemple

Pour tester si chien et niche sont des anagrammes :

  • on observe que c est bien dans niche
  • on teste si hien et nihe sont des anagrammes
  • on observe que h est bien dans nihe
  • on teste si ien et nie sont des anagrammes
  • ...
  • on observe que n et n sont égales : on renvoie True

Vous devez écrire deux fonctions :

  • supprime_premier(chaine, cible) renvoie un couple (present, chaine_sans_cible) dans lequel present est un booléen indiquant si le caractère cible est présent dans chaine et chaine_sans_cible la même chaine sans la première occurrence de cible
  • anagramme(chaine1, chaine2) renvoie True si les deux chaines sont des anagrammes, False sinon

On garantit que les deux chaines sont non vides.

🐍 Script Python
def supprime_premier(chaine, cible):
    ...


def anagrammes(chaine1, chaine2):
    ...

Exemples

🐍 Console Python
>>> supprime_premier('ukulélé', 'u')
(True, 'kulélé')
>>> supprime_premier('ukulélé', 'é')
(True, 'ukullé')
>>> supprime_premier('ukulélé', 'a')
(False, 'ukulélé')
>>> anagrammes('chien', 'niche')
True
>>> anagrammes('énergie noire', 'reine ignorée')
True
>>> anagrammes('louve', 'poule')
False
###
# Testsbksl-nlassert supprimepy-undpremier('ukulélé', 'u') == (True, 'kulélé')bksl-nlassert supprimepy-undpremier('ukulélé', 'é') == (True, 'ukullé')bksl-nlassert supprimepy-undpremier('ukulélé', 'a') == (False, 'ukulélé')bksl-nlassert anagrammes('chien', 'niche')bksl-nlassert anagrammes('énergie noire', 'reine ignorée')bksl-nlassert not anagrammes('louve', 'poule')bksl-nlbksl-nl# Tests supplémentairesbksl-nlassert supprimepy-undpremier('mississippi', 'm') == (True, 'ississippi')bksl-nlassert supprimepy-undpremier('mississippi', 'a') == (False, 'mississippi')bksl-nlassert anagrammes('nsi', 'isn')bksl-nlassert not anagrammes('nsi', 'snt')bksl-nlassert anagrammes('clint eastwood', 'old west action')bksl-nlassert anagrammes('astronomers ', 'moon starers')bksl-nlassert not anagrammes('astronome', 'metronome')bksl-nlbksl-nl 5/5

def supprimepy-undpremier(chaine, cible):bksl-nl ...bksl-nlbksl-nlbksl-nldef anagrammes(chaine1, chaine2):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert supprimepy-undpremier('ukulélé', 'u') == (True, 'kulélé')bksl-nlassert supprimepy-undpremier('ukulélé', 'é') == (True, 'ukullé')bksl-nlassert supprimepy-undpremier('ukulélé', 'a') == (False, 'ukulélé')bksl-nlassert anagrammes('chien', 'niche')bksl-nlassert anagrammes('énergie noire', 'reine ignorée')bksl-nlassert not anagrammes('louve', 'poule')bksl-nlbksl-nlNone

A

Z

Retour en haut de la page