Reverse a String

Q: Quelle est la complexité temporelle de l’inversion d’une chaîne de caractères ?

Inverser prend un temps de O(n) , car chaque caractère doit être déplacé vers une nouvelle position et chacun est traité une fois. Construire une nouvelle chaîne nécessite un espace supplémentaire de O(n) . L’échange avec deux pointeurs ne nécessite qu’un espace supplémentaire de O(1) lorsque les caractères se trouvent déjà dans un tableau modifiable.

Q: Comment inverser une chaîne sans fonction intégrée d’inversion ?

Copiez les caractères dans un tableau, placez un pointeur à chaque extrémité, échangez les deux caractères et rapprochez les pointeurs jusqu’à ce qu’ils se rejoignent. Vous pouvez aussi parcourir les indices du dernier au premier et ajouter chaque caractère à un générateur de chaînes. Les deux méthodes produisent la chaîne inversée en un seul passage.

Q: Peux-tu inverser une chaîne sur place ?

Uniquement lorsque les caractères se trouvent dans un tampon modifiable, comme un tableau de char en C, Java ou C#, une liste en Python, ou une std::string en C++. Les chaînes de caractères en Java, Python, JavaScript et dans de nombreux autres langages sont immuables : vous les copiez donc dans un tableau, effectuez les échanges à l’intérieur de celui-ci, puis construisez une nouvelle chaîne. L’étape d’échange elle-même se fait sur place dans les deux cas.

Q: Pourquoi la boucle à deux pointeurs s’arrête-t-elle au milieu ?

Chaque échange place deux caractères à leur position finale, donc après n / 2 échanges, chaque caractère se trouve à sa place. Continuer au-delà du milieu échange à nouveau les mêmes paires et annule le travail effectué. Lorsque la longueur est impaire, le caractère du milieu se trouve déjà à son propre indice symétrique et n’a pas besoin d’être échangé.

DébutantTableaux et chaînes Deux pointeurs

+10

Vous recevez une chaîne s composée de lettres anglaises et de chiffres. Renvoyez une nouvelle chaîne contenant les mêmes caractères dans l’ordre inverse, de sorte que le dernier caractère passe en premier et que le premier passe en dernier. Conservez chaque caractère exactement tel quel, y compris sa casse.

Fonction

reverseString(s: string) → string

sstring: la chaîne à inverser
Renvoiestring: les caractères de s dans l’ordre inverse

Contraintes

1 ≤ s.length ≤ 10⁴
s ne contient que des lettres anglaises (a à z, A à Z) et des chiffres (0 à 9).

Exemples

Entrée: s = "Coddy2026"
Sortie: "6202yddoC"
Explication: Lisez Coddy2026 de son dernier caractère au premier : 6, 2, 0, 2, puis y, d, d, o et enfin le C majuscule.

Entrée: s = "noon"
Sortie: "noon"
Explication: noon est un palindrome, donc son inverse est le même mot. Les n extérieurs échangent leur place, puis les deux o font de même.

+14 tests cachés à la soumission

Pour aller plus loin

Comment inverserais-tu l’ordre des mots dans une phrase, en transformant hello big world en world big hello, tout en gardant les lettres de chaque mot dans l’ordre ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Chaque caractère a une destination fixe : celui à l’index i doit se trouver à l’index n-1-i. Tu peux écrire les caractères dans une nouvelle chaîne dans cet ordre, ou les échanger par paires en partant des deux extrémités. L’échange est la méthode que les intervieweurs demandent, car le même déplacement de deux pointeurs inverse un tableau sur place et permet de vérifier si une chaîne est un palindrome.

Copiez les caractères depuis l’arrière

Intuition

Le renversement de s commence par le dernier caractère de s, continue avec l’avant-dernier et se termine par le premier. Parcourez donc les indices de n-1 à 0 et ajoutez chaque caractère à la réponse au fur et à mesure. Pour Coddy2026, vous ajoutez 6, 2, 0, 2, y, et ainsi de suite, ce qui donne 6202yddoC.

Chaque caractère est lu une fois et écrit une fois, le travail est donc de O(n). La réponse est une deuxième chaîne de n caractères, ce qui représente un espace supplémentaire de O(n).

La façon dont vous ajoutez les caractères compte. Ajouter un caractère à une chaîne immuable avec + copie la chaîne entière à chaque fois, et pour n = 10^4, cela représente environ 5 × 10^7 copies de caractères. Rassemblez les caractères dans une liste ou un constructeur de chaîne, puis réunissez-les une seule fois à la fin.

Algorithme

Crée une liste vide ou un constructeur de chaîne pour la réponse.
Parcours i de n-1 jusqu’à 0.
Ajoute s[i] à la réponse.
Assemble la réponse en une chaîne et retourne-la.

def reverseString(s):
    result = []
    for i in range(len(s) - 1, -1, -1):
        result.append(s[i])
    return "".join(result)

Échangez les éléments des deux extrémités à l’aide de deux pointeurs

Intuition

Inverser consiste à apparier les caractères de l’extérieur vers l’intérieur. Le premier et le dernier échangent leurs places, puis le deuxième et l’avant-dernier, et ainsi de suite vers le milieu. Place un pointeur left à l’index 0 et un pointeur right à l’index n-1, échange les deux caractères, puis déplace les deux pointeurs d’un pas vers l’intérieur.

Arrête-toi lorsque les pointeurs se rencontrent ou se croisent. Dans noon, les pointeurs commencent aux positions 0 et 3, puis passent à 1 et 2, et se croisent ensuite, après deux échanges. Avec une longueur impaire, comme xYz, ils se rencontrent sur le caractère du milieu, qui est déjà à sa place définitive et n’est donc jamais touché. Chaque échange place deux caractères à leur place définitive, donc n / 2 échanges suffisent.

Les échanges eux-mêmes ne nécessitent qu’une variable temporaire, soit un espace supplémentaire de O(1). La plupart des langages ne permettent pas de modifier une chaîne sur place ; il faut donc d’abord la copier dans un tableau de caractères, ce qui coûte O(n). Lors d’un entretien où l’entrée est déjà un tableau de caractères, cette méthode inverse celui-ci sans aucune mémoire supplémentaire.

Algorithme

Copiez s dans un tableau de caractères.
Définissez left = 0 et right = n-1.
Tant que left < right, échangez les caractères aux positions left et right, puis ajoutez 1 à left et soustrayez 1 à right.
Transformez le tableau en chaîne de caractères et renvoyez-la.

def reverseString(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return "".join(chars)

Pièges et cas limites

Inverser semble tenir sur une ligne, mais les bogues se cachent dans les limites de la boucle et dans la façon de construire le résultat.

Faire parcourir à left toute la chaîne jusqu’à n-1. Au-delà du milieu, chaque paire est échangée une deuxième fois et la chaîne retrouve son état initial. Arrêtez-vous à left < right.
Commencer la boucle à rebours à n au lieu de n-1, ce qui lit une position au-delà de la fin. En Lua et en R, les indices vont de 1 à n.
Construire le résultat avec result = result + ch sur une chaîne immuable. À chaque étape, tout le contenu déjà obtenu est recopié, ce qui transforme une tâche linéaire en une tâche quadratique pour les longues entrées.
Oublier le caractère de terminaison '\0' en C. Un tampon de n octets est trop court d’un octet ; allouez n + 1.
Échanger sans variable temporaire : après chars[left] = chars[right], l’ancien caractère de gauche est perdu, sauf si votre langage échange les deux valeurs simultanément.

Questions fréquentes4

Quelle est la complexité temporelle de l’inversion d’une chaîne de caractères ?

Inverser prend un temps de O(n), car chaque caractère doit être déplacé vers une nouvelle position et chacun est traité une fois. Construire une nouvelle chaîne nécessite un espace supplémentaire de O(n). L’échange avec deux pointeurs ne nécessite qu’un espace supplémentaire de O(1) lorsque les caractères se trouvent déjà dans un tableau modifiable.

Comment inverser une chaîne sans fonction intégrée d’inversion ?

Copiez les caractères dans un tableau, placez un pointeur à chaque extrémité, échangez les deux caractères et rapprochez les pointeurs jusqu’à ce qu’ils se rejoignent. Vous pouvez aussi parcourir les indices du dernier au premier et ajouter chaque caractère à un générateur de chaînes. Les deux méthodes produisent la chaîne inversée en un seul passage.

Peux-tu inverser une chaîne sur place ?

Uniquement lorsque les caractères se trouvent dans un tampon modifiable, comme un tableau de char en C, Java ou C#, une liste en Python, ou une std::string en C++. Les chaînes de caractères en Java, Python, JavaScript et dans de nombreux autres langages sont immuables : vous les copiez donc dans un tableau, effectuez les échanges à l’intérieur de celui-ci, puis construisez une nouvelle chaîne. L’étape d’échange elle-même se fait sur place dans les deux cas.

Pourquoi la boucle à deux pointeurs s’arrête-t-elle au milieu ?

Chaque échange place deux caractères à leur position finale, donc après n / 2 échanges, chaque caractère se trouve à sa place. Continuer au-delà du milieu échange à nouveau les mêmes paires et annule le travail effectué. Lorsque la longueur est impaire, le caractère du milieu se trouve déjà à son propre indice symétrique et n’a pas besoin d’être échangé.

Python

def reverseString(s):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "Coddy2026"

Attendu

"6202yddoC"