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

Que diriez-vous de...

var words = "My name is X Y Z";
var wr = String.Join( " ", words.Split(' ').Reverse().ToArray() );

Je suppose que ce n'est pas en ligne tho.

Answer 2

En c, c'est ainsi que vous pourriez le faire, O(N) et en utilisant seulement O(1) structures de données (i.e. un char).

#include<stdio.h>
#include<stdlib.h>
main(){
  char* a = malloc(1000);
  fscanf(stdin, "%[^\0\n]", a);
  int x = 0, y;
  while(a[x]!='\0')
  {
    if (a[x]==' ' || a[x]=='\n')
    {
      x++;
    }
    else
    {
      y=x;
      while(a[y]!='\0' && a[y]!=' ' && a[y]!='\n')
      { 
        y++;
      }
      int z=y;
      while(x<y)
      {
        y--;
        char c=a[x];a[x]=a[y];a[y]=c; 
        x++;
      }
      x=z;
    }
  }

  fprintf(stdout,a);
  return 0;
}

Answer 3

import java.util.Scanner;

public class revString {
   static char[] str;

   public static void main(String[] args) {
    //Initialize string
    //str = new char[] { 'h', 'e', 'l', 'l', 'o', ' ', 'a', ' ', 'w', 'o',
    //'r', 'l', 'd' };
    getInput();

    // reverse entire string
    reverse(0, str.length - 1);

    // reverse the words (delimeted by space) back to normal
    int i = 0, j = 0;
    while (j < str.length) {

        if (str[j] == ' ' || j == str.length - 1) {

            int m = i;
            int n;

            //dont include space in the swap. 
            //(special case is end of line)
            if (j == str.length - 1)
                n = j;
            else
                n = j -1;

            //reuse reverse
            reverse(m, n);

            i = j + 1;

        }
        j++;
    }

    displayArray();
}

private static void reverse(int i, int j) {

    while (i < j) {

        char temp;
        temp = str[i];
        str[i] = str[j];
        str[j] = temp;

        i++;
        j--;
    }
}
private static void getInput() {
    System.out.print("Enter string to reverse: ");
    Scanner scan = new Scanner(System.in);
    str = scan.nextLine().trim().toCharArray(); 
}

private static void displayArray() {
    //Print the array
    for (int i = 0; i < str.length; i++) {
        System.out.print(str[i]);
    }
}

}

Answer 4

Cela peut être fait plus simplement en utilisant sscanf :

void revertWords(char *s);
void revertString(char *s, int start, int n);
void revertWordsInString(char *s);

void revertString(char *s, int start, int end)
{
     while(start<end)
     {
         char temp = s[start];
         s[start] = s[end];
         s[end]=temp;
         start++;
         end --;
     }
}

void revertWords(char *s)
{
  int start = 0;

  char *temp = (char *)malloc(strlen(s) + 1);
  int numCharacters = 0;
  while(sscanf(&s[start], "%s", temp) !=EOF)
  {
      numCharacters = strlen(temp);

      revertString(s, start, start+numCharacters -1);
      start = start+numCharacters + 1;
      if(s[start-1] == 0)
      return;

  }
  free (temp);

}

void revertWordsInString(char *s)
{
   revertString(s,0, strlen(s)-1);
   revertWords(s);
}

int main()
{
   char *s= new char [strlen("abc deff gh1 jkl")+1];
   strcpy(s,"abc deff gh1 jkl");
   revertWordsInString(s);
   printf("%s",s);
   return 0;
}

Answer 5

En Java, en utilisant une chaîne supplémentaire (avec StringBuilder) :

public static final String reverseWordsWithAdditionalStorage(String string) {
    StringBuilder builder = new StringBuilder();

    char c = 0;
    int index = 0;
    int last = string.length();
    int length = string.length()-1;
    StringBuilder temp = new StringBuilder();
    for (int i=length; i>=0; i--) {
        c = string.charAt(i);
        if (c == SPACE || i==0) {
            index = (i==0)?0:i+1;
            temp.append(string.substring(index, last));
            if (index!=0) temp.append(c);
            builder.append(temp);
            temp.delete(0, temp.length());
            last = i;
        }
    }

    return builder.toString();
}

En Java in-place :

public static final String reverseWordsInPlace(String string) {
    char[] chars = string.toCharArray();

    int lengthI = 0;
    int lastI = 0;
    int lengthJ = 0;
    int lastJ = chars.length-1;

    int i = 0;
    char iChar = 0;
    char jChar = 0;
    while (i<chars.length && i<=lastJ) {
        iChar = chars[i];
        if (iChar == SPACE) {
            lengthI = i-lastI;
            for (int j=lastJ; j>=i; j--) {
                jChar = chars[j];
                if (jChar == SPACE) {
                    lengthJ = lastJ-j;
                    swapWords(lastI, i-1, j+1, lastJ, chars);
                    lastJ = lastJ-lengthI-1;
                    break;
                }
            }
            lastI = lastI+lengthJ+1;
            i = lastI;
        } else {
            i++;
        }
    }

    return String.valueOf(chars);
}

private static final void swapWords(int startA, int endA, int startB, int endB, char[] array) {
    int lengthA = endA-startA+1;
    int lengthB = endB-startB+1;

    int length = lengthA;
    if (lengthA>lengthB) length = lengthB;

    int indexA = 0;
    int indexB = 0;
    char c = 0;
    for (int i=0; i<length; i++) {
        indexA = startA+i;
        indexB = startB+i;

        c = array[indexB];
        array[indexB] = array[indexA];
        array[indexA] = c;
    }

    if (lengthB>lengthA) {
        length = lengthB-lengthA;
        int end = 0;
        for (int i=0; i<length; i++) {
            end = endB-((length-1)-i);
            c = array[end];
            shiftRight(endA+i,end,array);
            array[endA+1+i] = c;
        }
    } else if (lengthA>lengthB) {
        length = lengthA-lengthB;
        for (int i=0; i<length; i++) {
            c = array[endA];
            shiftLeft(endA,endB,array);
            array[endB+i] = c;
        }
    }
}

private static final void shiftRight(int start, int end, char[] array) {
    for (int i=end; i>start; i--) {
        array[i] = array[i-1];
    }
}

private static final void shiftLeft(int start, int end, char[] array) {
    for (int i=start; i<end; i++) {
        array[i] = array[i+1];
    }
}