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

Utilisation de Java :

String newString = "";
String a = "My name is X Y Z";
    int n = a.length();
    int k = n-1;
    int j=0;

    for (int i=n-1; i>=0; i--)
    {
        if (a.charAt(i) == ' ' || i==0)
        {

            j= (i!=0)?i+1:i;

            while(j<=k)
            {
                newString = newString + a.charAt(j);
                j=j+1;
            }
            newString = newString + " ";
            k=i-1;
        }

    }
    System.out.println(newString);

La complexité est de O(n) [parcourir le tableau entier] + O(n) [parcourir à nouveau chaque mot] = O(n)

Answer 2

Voici une petite astuce pour ceux qui ont aimé la question... que se passe-t-il si l'alphabet comprenant les mots échangés est plus petit que 16 caractères (16 incluant l'espace) ? il existe de nombreux exemples de tels alphabets : les caractères numériques [01234567890.-+] , les lettres du génome [GATC] , l'alphabet hawaïen [aeiouhklmnpv ?], le code morse [-.] , les notes de musique [ABCDEFG#m], etc. Cela permet de coder les caractères comme des nibbles (4bits) et de stocker deux caractères codés dans un caractère de 8 bits.

Il n'est toujours pas trivial de faire l'échange de mots dans une seule boucle avec un curseur qui se déplace de gauche à droite et l'autre de droite à gauche. Il y a en fait 4 types de copie de mots : copier un mot du côté gauche de la chaîne vers la droite, du côté droit de la chaîne vers la gauche et les deux copies équivalentes qui impliquent un chevauchement en lecture/écriture : position X->X+y et X->X-y, où y est inférieur à la longueur de X.

La bonne optimisation est que pendant la première moitié de la boucle, les mots de la partie droite sont encodés dans la partie gauche (en conservant les valeurs originales de la partie gauche), mais ensuite, dans la deuxième moitié, les mots de la partie gauche peuvent être copiés directement dans la partie droite, puis les caractères de la partie gauche sont réécrits avec leurs valeurs finales...

Voici le code C, qui prend n'importe quel alphabet comme paramètre :

#define WORDS_DELIMITER  ' '
#define UNMAPPED         0xFF

#define BITS_IN_NIBBLE   4
#define BITS_IN_BYTE     8
#define CHARS_IN_NIBBLE  (1 << BITS_IN_NIBBLE)
#define CHARS_IN_BYTE    (1 << BITS_IN_BYTE)

typedef union flip_char_ {
    unsigned char clear;
    struct {
        unsigned char org:4;
        unsigned char new:4;
    } encoded;
} flip_char_t;

typedef struct codec_ {
    unsigned char nibble2ascii[CHARS_IN_NIBBLE];
    unsigned char ascii2nibble[CHARS_IN_BYTE];
} codec_t;

static int 
codec_init (const unsigned char *alphabet, codec_t *codec)
{
size_t len = strlen(alphabet), i;

if (len > CHARS_IN_NIBBLE) {
    fprintf(stderr, "alphabet is too long!\n");
    return -1;
}
if (strchr(alphabet, WORDS_DELIMITER) == NULL) {
    fprintf(stderr, "missing space in the alphabet\n");
    return -1;
}
strcpy(codec->nibble2ascii, alphabet);
memset(codec->ascii2nibble , UNMAPPED, CHARS_IN_BYTE);
for (i=0; i<len; i++) {
    codec->ascii2nibble[ alphabet[i] ] = i;
}
return 0;
}

static inline int
is_legal_char (const codec_t *codec, const unsigned char ch)
{
return codec->ascii2nibble[ch] != UNMAPPED;
}

static inline unsigned char 
encode_char (const codec_t *codec, unsigned char org, unsigned char new)
{
flip_char_t flip;
flip.encoded.org = codec->ascii2nibble[org];
flip.encoded.new = codec->ascii2nibble[new];
return flip.clear;
} 

static inline unsigned char 
decode_org (const codec_t *codec, unsigned char ch)
{
flip_char_t flip = { .clear = ch };
return codec->nibble2ascii[flip.encoded.org];
}

static inline unsigned char 
decode_new (const codec_t *codec, unsigned char ch)
{
flip_char_t flip = { .clear = ch };
return codec->nibble2ascii[flip.encoded.new];
}

// static void inline
// encode_char (const char *alphabet, const char *
static int 
flip_words (const unsigned char *alphabet, unsigned char *a, size_t len)
{
codec_t codec;     /* mappings of the 16char-alphabet to a nibble */
int r=len-1;       /* right/reader cursor: moves from right to left scanning for words */
int l=0;           /* left/writer cursor: moves from left to right */
int i=0;                      /* word iterator */
int start_word=-1,end_word=-1; /* word boundaries */
unsigned char org_r=0;        /* original value pointed by the right cursor */
int encode=0, rewrite=0;      /* writing states */

if (codec_init(alphabet, &codec) < 0) return -1;

/* parse the buffer from its end backward */
while (r>=0) {
    if (r>=l && !is_legal_char(&codec, a[r])) {
        fprintf(stderr, "illegal char %c in string\n", a[r]);
        return -1;
    }
    /* read the next charachter looking for word boundaries */
    org_r = (r<l) ? decode_org(&codec, a[r]) : a[r];
    /* handle word boundaries */
    if (org_r == WORDS_DELIMITER) {
        /* mark start of word: next char after space after non-space  */ 
        if (end_word>0 && start_word<0) start_word = r/*skip this space*/+1;
        /* rewrite this space if necessary (2nd half) */
        if (r<l) a[r] = decode_new(&codec,a[r]);
    } else {
        /* mark end of word: 1st non-space char after spaces */ 
        if (end_word<0) end_word = r;
        /* left boundary is a word boundary as well */
        if (!r) start_word = r;
    }
    /* Do we have a complete word to process? */
    if (start_word<0 || end_word<0) {
        r--;
        continue;
    }
    /* copy the word into its new location */
    for(i=start_word; i<=end_word; i++, l++) {
        if (i>=l && !is_legal_char(&codec, a[l])) {
            fprintf(stderr, "illegal char %c in string\n", a[l]);
            return -1;
        }
        /* reading phase: value could be encoded or not according to writer's position */
        org_r= (i<l) ? decode_org(&codec, a[i]) : a[i];
        /* overlapping words in shift right: encode and rewrite */
        encode=rewrite=(l>=start_word && l<=end_word && i<l);
        /* 1st half - encode both org and new vals */
        encode|=(start_word-1>l);
        /* 2nd half - decode and rewrite final values */
        rewrite|=(i<l);
        /* writing phase */
        a[l]= encode ? encode_char(&codec, a[l], org_r) : org_r;
        if (rewrite) {
            a[i]=decode_new(&codec, a[i]);
        }
    }
    /* done with this word! */
    start_word=end_word=-1;
    /* write a space delimiter, unless we're at the end */
    if (r) {
        a[l] = l<r ? encode_char(&codec, a[l], WORDS_DELIMITER) : WORDS_DELIMITER;
        l++;
    }
    r--;
}
a[l]=0;
return 0; /* All Done! */
}

Answer 3

La façon la plus simple de le faire..

          string inputStr = "My name is X Y Z";
          string outputStr = string.Empty;
          List<string> templist1 = new List<string>();
          templist1 = inputStr.Split(' ').ToList();
           for (int i = templist1.Count- 1 ; i >= 0; i--)
          {
              if (outputStr != string.Empty)
              {
                  outputStr = outputStr + " " + templist1[i];
              }
              else
              {
                  outputStr = templist1[i];
              }
          }

           Console.WriteLine("Reverse of a String is", outputStr);

        Output:
        Z Y X is name My

Answer 4

public class reversewords {

public static void main(String args[])

{

String s="my name is nimit goyal";

    char a[]=s.toCharArray();
    int x=s.length();
    int count=0;
    for(int i=s.length()-1 ;i>-1;i--)
    { 
        if(a[i]==' ' ||i==0)
        { //System.out.print("hello");
            if(i==0)
            {System.out.print(" ");}
            for(int k=i;k<x;k++)
            {
                System.out.print(a[k]);
                count++;
            }
            x=i;

        }count++;

    }
    System.out.println("");
    System.out.println("total run =="+count);
}

}

sortie : goyal nimit est mon nom

course totale ==46

Answer 5

Voici l'algorithme :

1. Explosez la chaîne avec de l'espace et créez un tableau de mots.
2. Inversez le tableau.
3. Implante le tableau par l'espace.