Algorithm Language Agnostic Reverse Puzzle

Renvoyer Efficacement l’Ordre des Mots dans un Tableau de Caractères

Renvoyer l’ordre des mots dans un tableau de caractères est un problème classique qui teste votre compréhension des algorithmes et de la manipulation de chaînes. Que vous vous prépariez pour un entretien ou que vous affiniez simplement vos compétences en programmation, maîtriser ce défi est très gratifiant. Dans cet article, nous allons explorer le problème en détail et décomposer une solution efficace en C/C++.

Le Problème

Étant donné un tableau de caractères formant une phrase, notre objectif est de renverser l’ordre des mots sans altérer les lettres individuelles dans les mots. Par exemple, si vous saisissez :

"this is a string"

La sortie devrait être :

'string a is this'

Le défi spécifie que cette opération doit être réalisée en temps O(N) et espace O(1), ce qui signifie que vous ne pouvez pas utiliser des fonctions comme split() ou des structures de données comme des piles qui manipulent un espace supplémentaire.

Analyse du Problème

Complexité Temporelle

L’exigence pour une complexité temporelle O(N) signifie que l’algorithme doit effectuer un passage linéaire à travers les données. Par conséquent, nous devrions éviter les boucles imbriquées qui augmentent la complexité temporelle.

Complexité Spatiale

Pour une complexité spatiale O(1), nous ne pouvons pas utiliser de structures de données supplémentaires pour le stockage. Cela signifie que les opérations doivent avoir lieu directement dans le tableau d’entrée.

La Solution

Décomposons la solution étape par étape. Nous allons utiliser une approche en deux passes pour résoudre ce problème efficacement.

Étape 1 : Inverser la Chaîne Complète

La première étape consiste à inverser l’ensemble du tableau. Cela transforme la chaîne originale en une chaîne où tous les caractères sont inversés. Pour notre exemple "this is a string" après inversion :

"gnirts a si siht"

Étape 2 : Inverser Chaque Mot

Maintenant que nous avons inversé l’ensemble de la chaîne, nous devons inverser chaque mot individuel pour les remettre dans le bon ordre. Voici comment nous pouvons implémenter ces étapes en C/C++ :

void swap(char* str, int i, int j) {
    char t = str[i];
    str[i] = str[j];
    str[j] = t;
}

void reverse_string(char* str, int length) {
    for(int i = 0; i < length / 2; i++) {
        swap(str, i, length - i - 1);
    }
}

void reverse_words(char* str) {
    int l = strlen(str);
    // Inverser toute la chaîne
    reverse_string(str, strlen(str));
    int p = 0;

    // Trouver les limites des mots et inverser mot par mot
    for(int i = 0; i < l; i++) {
        if(str[i] == ' ') {
            reverse_string(&str[p], i - p);  // Inverser le mot identifié
            p = i + 1;
        }
    }
    // Enfin, inverser le dernier mot.
    reverse_string(&str[p], l - p);
}

Explication du Code

  1. Fonction Swap : Nous utilisons une fonction d’assistance swap pour interchanger des caractères dans le tableau.
  2. Fonction Reverse String : Cette fonction inverse les caractères de la chaîne à l’aide de la fonction swap.
  3. Fonction Reverse Words : La fonction principale inverse d’abord l’ensemble du tableau de caractères, puis itère à travers celui-ci pour inverser les mots individuels identifiés par les espaces. Le dernier mot est traité après la fin de la boucle.

Analyse de la Complexité

L’inversion à travers le tableau deux fois rend la complexité temporelle O(N) :

  • Premier passage : O(N) pour inverser la chaîne entière.
  • Deuxième passage : O(N) pour inverser chaque mot.

Ainsi, la complexité temporelle finale reste O(N). La complexité spatiale est O(1) car aucun espace supplémentaire n’est utilisé en dehors des variables pour l’itération.

Conclusion

Renvoyer l’ordre des mots dans un tableau de caractères efficacement nécessite une combinaison de manipulations de chaînes et une compréhension de l’accès indexé. L’algorithme présenté ici démontre une approche claire qui respecte les exigences de temps O(N) et d’espace O(1) tout en utilisant C/C++. Pratiquez cette solution, et vous trouverez que c’est un excellent ajout à votre boîte à outils de programmation !