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

Je sais qu'il y a plusieurs réponses correctes. Voici celle en C que j'ai trouvée. C'est une implémentation de la réponse excepté. La complexité en temps est O(n) et aucune chaîne supplémentaire n'est utilisée.

#include<stdio.h>

char * strRev(char *str, char tok)
{
   int len = 0, i;
   char *temp = str;
   char swap;

   while(*temp != tok && *temp != '\0') {
      len++; temp++;
   }   
   len--;

   for(i = 0; i < len/2; i++) {
      swap = str[i];
      str[i] = str[len - i]; 
      str[len - i] = swap;
   }   

   // Return pointer to the next token.
   return str + len + 1;
}

int main(void)
{
   char a[] = "Reverse this string.";
   char *temp = a;

   if (a == NULL)
      return -1; 

   // Reverse whole string character by character.
   strRev(a, '\0');

   // Reverse every word in the string again.
   while(1) {
      temp = strRev(temp, ' ');
      if (*temp == '\0')
         break;

      temp++;
   }   
   printf("Reversed string: %s\n", a); 
   return 0;
}

Answer 2

Utilisation

char str[50] = {0};
strcpy(str, (char*)"My name is Khan");
reverseWords(str);

Méthode

void reverseWords(char* pString){
    if(NULL ==pString){
        return;
    }
    int nLen     = strlen(pString);
    reverseString(pString,nLen);
    char* start  = pString;
    char* end    = pString;
    nLen         = 0;
    while (*end) {
        if(*end == ' ' ){
            reverseString(start,nLen);
            end++;
            start = end;
            nLen  = 0;
            continue;
        }
        nLen++;
        end++;
    }
    reverseString(start,nLen);
    printf("\n Reversed: %s",pString);

}

void reverseString(char* start,int nLen){
    char* end = start+ nLen-1;
    while(nLen > 0){
        char temp = *start;
        *start    = *end;
        *end      = temp;
        end--;
        start++;
        nLen-=2;
    }
}

Answer 3

C'est ainsi que vous le résolvez en TCL, peu importe le nombre d'espaces, de tabulations ou de nouvelles lignes ( \n ) existent dans votre chaîne de caractères. Il s'agit d'une solution de la vie réelle et de la façon de penser humaine. Elle ne considère pas qu'un et un seul espace est la marque d'un nouveau mot.

Et je pense qu'en C/C++ et Java, vous pouvez le traduire de la même manière.

J'ai travaillé dessus pendant deux jours avant cette publication, parce que je n'acceptais pas qu'il existe des fonctions fournies par la bibliothèque du langage qui sont aussi faites pour nous, et que nous n'utilisons pas.

<!-- language: lang-php -->
# 1- Reverse the orignial text
set reversed [ string reverse  $all_original_text] 

# 2- split the reversed string $reversed into a list of words then loop over them
set list_of_reversed_words [split $reversed  ]

foreach reversed_words $list_of_reversed_words {

# 3- find the indices of the extremes of each reversed word in the $reversed

set word_start [ string first $reversed_words $reversed $word_start]
set word_end [ expr $word_start -1 + [string length $letter] ]

# 4- reverse the current-in-the-loop reversed word back to its normal state, e.g: 
# if i have a word "loohcs" then convert it by reversing it to "school"

set original_word [string reverse [ string range $reversed $word_start $word_end] ]

# 5- replace  the reversed word (loohcs) with the correcte one (school)

set reversed [ string replace $reversed $word_start $word_end $original_word]

# 6- set the start-of-search index to the index 
# directly after the ending of the current word

set word_start [expr $word_end +1]

# 7-continue to the next loop  
}

#print the result
puts "finally: $reversed"

Answer 4

public class StringReverse {

  public static void main(String[] args) {

    StringReverse sr =new StringReverse();
    String output=sr.reverse("reverse this string");

    String substring="";
    for(int i=0;i<=output.length();i++)
        {
        if(i==output.length()){
            System.out.print(sr.reverse(substring));
            substring="";
        }else if(output.charAt(i)==' ' ){
            System.out.print(sr.reverse(substring+" "));
            substring="";

        }
        if(i<output.length())
        {
        substring+=output.charAt(i);}
        }

}

public String reverse(String str){
    char[] value=str.toCharArray();
    int count=str.length();
    int n = count - 1;
    for (int j = (n-1) >> 1; j >= 0; --j) {
        char temp = value[j];
        value[j] = value[n - j];
        value[n - j] = temp;
    }
    return new String(value);
  }
}

Answer 5

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

void reverse(char *data, int len) {
    int counter = 0;
    int end = len - 1;
    char temp;

    for (counter = 0; counter < len / 2; counter++, end--) {
        temp = data[counter];
        data[counter] = data[end];
        data[end] = temp;
    }
}

int main(void) {
    char data[] = "This is a line and needs to be reverse by words!";
    int c = 0;
    int len = strlen(data);
    int wl = 0;
    int start = 0;
    printf("\n    data =  %s", data);
    reverse(data, len);

    for (c = 0; c < len; c++) {
        if (!wl) {
            start = c;
        }
        if (data[c] != ' ') {
            wl++;
        } else {
            reverse(data + start, wl);
            wl = 0;
        }

    }

    printf("\nnow data =  %s", data);
    return EXIT_SUCCESS;
}