Reverse Words in a String

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

Les deux approches s’exécutent en un temps de O(n) pour une chaîne de longueur n , car chaque caractère est lu et écrit un nombre constant de fois. Le découpage utilise un espace supplémentaire de O(n) pour la liste de mots. Inverser la chaîne entière puis chaque mot nécessite un espace supplémentaire de O(1) sur un tableau de caractères que tu peux modifier.

MoyenTableaux et chaînes Deux pointeurs

+10

On vous donne une chaîne de caractères s composée de mots et d’espaces. Un mot est une suite de lettres et de chiffres sans espace à l’intérieur. Les mots peuvent être séparés par plusieurs espaces, et s peut commencer ou se terminer par des espaces.

Renvoyez les mots dans l’ordre inverse, séparés par exactement un espace, sans espace au début ni à la fin. Chaque mot conserve son orthographe ; seul l’ordre des mots change.

Fonction

reverseWords(s: string) → string

sstring: lettres, chiffres et espaces contenant au moins un mot
Renvoiestring: les mots de s dans l’ordre inverse, séparés par des espaces simples

Contraintes

1 ≤ s.length ≤ 10⁴
s ne contient que des lettres de l’alphabet anglais, des chiffres et des espaces.
s contient au moins un mot.

Exemples

Entrée: s = "Coddy runs in 15 languages"
Sortie: "languages 15 in runs Coddy"
Explication: Les mots sont Coddy, runs, in, 15 et languages. Lus de la fin au début, ils donnent languages 15 in runs Coddy ; 15 compte comme un mot, car les mots peuvent contenir des chiffres.

Entrée: s = " practice makes progress "
Sortie: "progress makes practice"
Explication: Les espaces aux deux extrémités sont supprimés, et les suites de deux et trois espaces entre les mots sont réduites à un seul espace. Les trois mots ressortent dans l’ordre inverse : progress makes practice.

Entrée: s = " single "
Sortie: "single"
Explication: Une liste d’un seul mot se lit de la même façon à l’envers. Seuls les espaces qui l’entourent disparaissent, donc la réponse est single.

Pour aller plus loin

Peux-tu inverser les mots tout en conservant l’espacement de s : les mêmes suites d’espaces, avec les mêmes longueurs, dans le même ordre ?

Solution

L’ordre des mots correspond à une inversion ; ce sont les espaces qui compliquent les solutions. Les espaces aux deux extrémités et les espaces répétés entre les mots doivent disparaître, avec exactement un espace entre les mots dans la réponse. Tu peux découper la chaîne en une liste de mots, ou inverser la chaîne entière, puis chaque mot dans un seul tableau.

Séparez en mots et réunissez-les dans l’ordre inverse

Intuition

Découpez s en mots, inversez la liste et assemblez-la avec des espaces simples. Le découpage demande de l’attention : découper " practice makes progress " à chaque espace donne six éléments vides autour des trois mots. Supprimez les éléments vides, et la liste contient practice, makes, progress.

Le découpage parcourt chaque caractère une fois et l’assemblage écrit chaque caractère conservé une fois, donc le temps d’exécution est O(n) pour une chaîne de longueur n. La liste de mots et la réponse occupent un espace supplémentaire de O(n).

Algorithme

Découpe s sur les espaces.
Supprime les éléments vides.
Inverse la liste de mots.
Réunis les mots en les séparant par un espace et renvoie le résultat.

def reverseWords(s):
    # split() with no argument treats any run of spaces as one separator
    # and ignores spaces at both ends.
    words = s.split()
    words.reverse()
    return " ".join(words)

Inversez toute la chaîne, puis chaque mot

Intuition

Inverser toute la chaîne place les mots dans le bon ordre, mais écrit chacun d’eux à l’envers : Coddy runs in 15 languages devient segaugnal 51 ni snur yddoC. Inverser ensuite chaque mot individuellement donne languages 15 in runs Coddy.

Les espaces sont traités lors du même passage. Un index read parcourt le tableau inversé et ignore les espaces ; un index write indique où placer le prochain caractère conservé. La copie n’écrase jamais un caractère dont vous avez encore besoin, car write ne dépasse jamais read : l’espace écrit avant un mot remplace au moins un espace ignoré par read.

Chaque caractère est copié au plus une fois et échangé au plus deux fois, donc le temps d’exécution est en O(n), avec un espace supplémentaire en O(1) sur un tampon de caractères que vous pouvez modifier. Ici, les chaînes arrivent sous forme de valeurs, donc chaque solution crée une copie de travail de s : la mémoire totale est en O(n).

Algorithme

Copiez s dans un tableau de caractères et inversez tout le tableau.
Parcourez le tableau avec un index de lecture et ignorez les espaces.
Pour chaque mot, écrivez d’abord un espace, sauf s’il s’agit du premier mot, puis copiez les caractères du mot à l’index d’écriture.
Inversez la portion copiée pour que le mot se lise dans le bon sens.
Renvoyez les write premiers caractères.

def reverseWords(s):
    chars = list(s)

    def reverse(lo, hi):
        while lo < hi:
            chars[lo], chars[hi] = chars[hi], chars[lo]
            lo += 1
            hi -= 1

    n = len(chars)
    reverse(0, n - 1)  # words in the right order, each spelled backwards
    write = 0
    read = 0
    while read < n:
        if chars[read] == " ":
            read += 1
            continue
        if write > 0:
            chars[write] = " "  # one space before every word but the first
            write += 1
        start = write
        while read < n and chars[read] != " ":
            chars[write] = chars[read]
            write += 1
            read += 1
        reverse(start, write - 1)  # spell the word forwards again
    return "".join(chars[:write])

Pièges et cas limites

Découper sur un seul espace et conserver chaque morceau. "a b" se découpe en a, un morceau vide et b, et la jointure remet deux espaces : "b a".
Penser qu’un découpage supprime les espaces aux extrémités. La méthode split(" ") de Java supprime les morceaux vides à la fin, mais les conserve au début ; ainsi, " a b" en laisse toujours un.
Ajouter un espace après chaque mot, y compris le dernier, de sorte que la réponse se termine par un espace. Placez l’espace avant chaque mot, sauf le premier.
N’effectuer qu’une seule inversion dans la version en place. Inverser uniquement les mots donne yddoC snur ni 51 segaugnal.
En PHP et en R, une entrée composée uniquement de chiffres, telle que 2026, peut être reçue comme un nombre. Convertissez-la en chaîne avant de la découper.

Questions fréquentes3

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

Les deux approches s’exécutent en un temps de O(n) pour une chaîne de longueur n, car chaque caractère est lu et écrit un nombre constant de fois. Le découpage utilise un espace supplémentaire de O(n) pour la liste de mots. Inverser la chaîne entière puis chaque mot nécessite un espace supplémentaire de O(1) sur un tableau de caractères que tu peux modifier.

Comment gérer plusieurs espaces entre les mots ?

Considérez un mot comme une suite de caractères non espacés et ne copiez jamais les espaces de l’entrée. Un découpage sans séparateur en Python et Ruby, strings.Fields en Go et split_whitespace en Rust ignorent déjà chaque suite d’espaces ainsi que les espaces aux deux extrémités ; ailleurs, supprimez les éléments vides. Insérez ensuite un espace entre les mots.

Peux-tu inverser les mots sans fonction split ?

Oui. Parcourez la chaîne depuis la droite : ignorez les espaces, repérez la fin d’un mot, déplacez-vous vers la gauche jusqu’à son début, puis ajoutez le mot en le précédant d’une espace, sauf s’il s’agit du premier. Chaque caractère est visité une seule fois, donc la complexité temporelle reste O(n), et les mots apparaissent dans l’ordre inverse sans avoir besoin d’inverser une liste.

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

Test #1

Test #2

Test #3

Argument

s = "Coddy runs in 15 languages"

Résultat attendu

"languages 15 in runs Coddy"