Inverser l'ordre des mots dans une chaîne de caractères

Question

J'ai ceci string s1 = "My name is X Y Z" et je veux inverser l'ordre des mots pour que s1 = "Z Y X is name My" .

Je peux le faire en utilisant un tableau supplémentaire. J'ai bien réfléchi mais est-il possible de le faire en place (sans utiliser de structures de données supplémentaires) et avec une complexité temporelle de O(n) ?

Answer 1

Voici l'implémentation Java :

public static String reverseAllWords(String given_string)
{
    if(given_string == null || given_string.isBlank())
        return given_string;

    char[] str = given_string.toCharArray();
    int start = 0;

    // Reverse the entire string
    reverseString(str, start, given_string.length() - 1);

    // Reverse the letters of each individual word
    for(int end = 0; end <= given_string.length(); end++)
    {
        if(end == given_string.length() || str[end] == ' ')
        {
            reverseString(str, start, end-1);
            start = end + 1;
        }
    }
    return new String(str);
}

// In-place reverse string method
public static void reverseString(char[] str, int start, int end)
{
    while(start < end)
    {
        char temp = str[start];
        str[start++] = str[end];
        str[end--] = temp;
    }
}

Answer 2

Ce n'est pas parfait mais ça marche pour moi en ce moment. Je ne sais pas si elle a un temps d'exécution O(n) (je l'étudie encore ^^) mais elle utilise un tableau supplémentaire pour accomplir la tâche.

Ce n'est probablement pas la meilleure réponse à votre problème car j'utilise une chaîne dest pour sauvegarder la version inversée au lieu de remplacer chaque mot dans la chaîne source. Le problème est que j'utilise une variable locale de la pile nommée buf pour copier tous les mots et je ne peux pas copier mais dans la chaîne source car cela conduirait à un crash si la chaîne source est de type const char *.

Mais c'était ma première tentative d'écrire une histoire comme celle-ci :) Ok, assez de blabla. Voici le code :

#include <iostream>
using namespace std;

void reverse(char *des, char * const s);
int main (int argc, const char * argv[])
{    
    char* s = (char*)"reservered. rights All Saints. The 2011 (c) Copyright 11/10/11 on Pfundstein Markus by Created";
    char *x = (char*)"Dogfish! White-spotted Shark, Bullhead";

    printf("Before: |%s|\n", x);
    printf("Before: |%s|\n", s);

    char *d = (char*)malloc((strlen(s)+1)*sizeof(char));  
    char *i = (char*)malloc((strlen(x)+1)*sizeof(char));

    reverse(d,s);
    reverse(i,x);

    printf("After: |%s|\n", i);
    printf("After: |%s|\n", d);

    free (i);
    free (d);

    return 0;
}

void reverse(char *dest, char *const s) {
    // create a temporary pointer
    if (strlen(s)==0) return;
    unsigned long offset = strlen(s)+1;

    char *buf = (char*)malloc((offset)*sizeof(char));
    memset(buf, 0, offset);

    char *p;
    // iterate from end to begin and count how much words we have
    for (unsigned long i = offset; i != 0; i--) {
        p = s+i;
        // if we discover a whitespace we know that we have a whole word
        if (*p == ' ' || *p == '\0') {
            // we increment the counter
            if (*p != '\0') {
                // we write the word into the buffer
                ++p;
                int d = (int)(strlen(p)-strlen(buf));
                strncat(buf, p, d);
                strcat(buf, " ");
            }
        }
    }

    // copy the last word
    p -= 1;
    int d = (int)(strlen(p)-strlen(buf));
    strncat(buf, p, d);
    strcat(buf, "\0");

    // copy stuff to destination string
    for (int i = 0; i < offset; ++i) {
        *(dest+i)=*(buf+i);
    }

    free(buf);
}

Answer 3

Nous pouvons insérer la chaîne dans une pile et lorsque nous extrairons les mots, ils seront dans l'ordre inverse.

void ReverseWords(char Arr[])
{
    std::stack<std::string> s;
    char *str;
    int length = strlen(Arr);
    str = new char[length+1];
    std::string ReversedArr;
    str = strtok(Arr," ");
    while(str!= NULL)
    {
        s.push(str);
        str = strtok(NULL," ");
    }
    while(!s.empty())
    {
        ReversedArr = s.top();
        cout << " " << ReversedArr;
        s.pop();
    }
}

Answer 4

Ce programme rapide fonctionne mais ne vérifie pas les cas particuliers.

#include <stdio.h>
#include <stdlib.h>
struct node
{
    char word[50];
    struct node *next;
};
struct stack
{
    struct node *top;
};
void print (struct stack *stk);
void func (struct stack **stk, char *str);
main()
{
    struct stack *stk = NULL;
    char string[500] = "the sun is yellow and the sky is blue";
    printf("\n%s\n", string);
    func (&stk, string);
    print (stk);
}
void func (struct stack **stk, char *str)
{
    char *p1 = str;
    struct node *new = NULL, *list = NULL;
    int i, j;
    if (*stk == NULL)
    {
        *stk = (struct stack*)malloc(sizeof(struct stack));
        if (*stk == NULL)
            printf("\n####### stack is not allocated #####\n");
        (*stk)->top = NULL;
    }
    i = 0;
    while (*(p1+i) != '\0')
    {
        if (*(p1+i) != ' ')
        {
            new = (struct node*)malloc(sizeof(struct node));
            if (new == NULL)
                printf("\n####### new is not allocated #####\n");
            j = 0;
            while (*(p1+i) != ' ' && *(p1+i) != '\0')
            {
                new->word[j] = *(p1 + i);
                i++;
                j++;
            }
            new->word[j++] = ' ';
            new->word[j] = '\0';
            new->next = (*stk)->top;
            (*stk)->top = new;
        }
        i++;
   }
}
void print (struct stack *stk)
{
    struct node *tmp = stk->top;
    int i;
    while (tmp != NULL)
    {
        i = 0;
        while (tmp->word[i] != '\0')
        {
            printf ("%c" , tmp->word[i]);
            i++;
        }
        tmp = tmp->next;
    }
    printf("\n");
}

Answer 5

public class manip{

public static char[] rev(char[] a,int left,int right) {
    char temp;
    for (int i=0;i<(right - left)/2;i++)    {
        temp = a[i + left];
        a[i + left] = a[right -i -1];
        a[right -i -1] = temp;
    }

    return a;
}
public static void main(String[] args) throws IOException {

    String s= "i think this works";
    char[] str = s.toCharArray();       
    int i=0;
    rev(str,i,s.length());
    int j=0;
    while(j < str.length) {
        if (str[j] != ' ' && j != str.length -1) {
            j++;
        } else
        {
            if (j == (str.length -1))   {
                j++;
            }
            rev(str,i,j);
            i=j+1;
            j=i;
        }
    }
    System.out.println(str);
}