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
etc
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,
- chaine_sans_cible la même chaine si cible n'est pas présent, la chaine privée de la première occurrence de cible si elle est présente
anagramme(chaine1, chaine2) renvoie True si les deux chaines sont des anagrammes, False sinon

On garantit que les deux chaines sont non vides.

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

###

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-nldef supprimepy-undpremier(chaine: str, cible: str) -> str:bksl-nl resultat = ""bksl-nl dejapy-undvu = Falsebksl-nl for caractere in chaine:bksl-nl if caractere == cible and not dejapy-undvu:bksl-nl dejapy-undvu = Truebksl-nl else:bksl-nl resultat += caracterebksl-nl return dejapy-undvu, resultatbksl-nlbksl-nlbksl-nldef anagrammes(chaine1: str, chaine2: str) -> bool:bksl-nl if len(chaine1) == 1:bksl-nl return chaine1 == chaine2bksl-nl else:bksl-nl cible = chaine1[0]bksl-nl vrai, chaine1py-undsanspy-undcible = supprimepy-undpremier(chaine1, cible)bksl-nl ciblepy-unddanspy-und2, chaine2py-undsanspy-undcible = supprimepy-undpremier(chaine2, cible)bksl-nl if ciblepy-unddanspy-und2:bksl-nl return anagrammes(chaine1py-undsanspy-undcible, chaine2py-undsanspy-undcible)bksl-nl else:bksl-nl return Falsebksl-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-nl

A

La fonction supprime_premier nécessite de distinguer plusieurs cas de figure :

le caractère lu est différent du caractère cherché : on le recopie
le caractère lu est égal au caractère cherché et il n'a pas encore été trouvé (present toujours à False) : on ne le recopie pas, mais on indique qu'on l'a trouvé et supprimé (present = True)
le caractère lu est égal au caractère cherché et il a déjà été trouvé/supprimé : on le recopie
on renvoie pour finir le couple (present, resultat)

Pour la fonction anagrammes :

si les deux chaines sont de longueur 1, on renvoie le résultat de leur comparaison (cas de base de la récursivité)
sinon, on supprime le premier caractère de chaine1 dans les deux chaines
chacun des appels supprime_premier(chaine, cible) renvoie la chaine réduite, mais aussi un booléen indiquant si la cible était présente dans la chaine
on se demande alors si cible était dans chaine2 (le premier caractère de chaine1 est nécessairement dans chaine1). On teste donc le booléen renvoyé par supprime_premier(chaine2, cible) :
- si c'est le cas, on appelle la fonction sur ces chaines "réduites"
- si ce n'est pas le cas, on renvoie False directement

Z