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

Inversez la chaîne entière, puis inversez les lettres de chaque mot.

Après le premier passage, la chaîne sera

s1 = "Z Y X si eman yM"

et après le deuxième passage, ce sera

s1 = "Z Y X is name My"

Answer 2

inverser la chaîne et ensuite, dans un deuxième temps, inverser chaque mot...

en c#, complètement in-place sans tableaux supplémentaires :

static char[] ReverseAllWords(char[] in_text)
{
    int lindex = 0;
    int rindex = in_text.Length - 1;
    if (rindex > 1)
    {
        //reverse complete phrase
        in_text = ReverseString(in_text, 0, rindex);

        //reverse each word in resultant reversed phrase
        for (rindex = 0; rindex <= in_text.Length; rindex++)
        {
            if (rindex == in_text.Length || in_text[rindex] == ' ')
            {
                in_text = ReverseString(in_text, lindex, rindex - 1);
                lindex = rindex + 1;
            }
        }
    }
    return in_text;
}

static char[] ReverseString(char[] intext, int lindex, int rindex)
{
    char tempc;
    while (lindex < rindex)
    {
        tempc = intext[lindex];
        intext[lindex++] = intext[rindex];
        intext[rindex--] = tempc;
    }
    return intext;
}

Answer 3

Not exactly in place, but anyway: Python:

>>> a = "These pretzels are making me thirsty"
>>> " ".join(a.split()[::-1])
'thirsty me making are pretzels These'

Answer 4

Dans Smalltalk :

'These pretzels are making me thirsty' subStrings reduce: [:a :b| b, ' ', a]

Je sais que personne ne s'intéresse à Smalltalk, mais c'est si beau pour moi.

Answer 5

Vous ne pouvez pas faire l'inversion sans au moins une structure de données supplémentaire. Je pense que la plus petite structure serait un seul caractère comme tampon pendant que vous échangez les lettres. On peut toujours considérer que c'est "en place", mais ce n'est pas complètement "sans structure de données supplémentaire".

Vous trouverez ci-dessous le code mettant en œuvre ce que Bill le Lézard décrit :

string words = "this is a test";

// Reverse the entire string
for(int i = 0; i < strlen(words) / 2; ++i) {
  char temp = words[i];
  words[i] = words[strlen(words) - i];
  words[strlen(words) - i] = temp;
}

// Reverse each word
for(int i = 0; i < strlen(words); ++i) {
  int wordstart = -1;
  int wordend = -1;
  if(words[i] != ' ') {
    wordstart = i;
    for(int j = wordstart; j < strlen(words); ++j) {
      if(words[j] == ' ') {
        wordend = j - 1;
        break;
      }
    }
    if(wordend == -1)
      wordend = strlen(words);
    for(int j = wordstart ; j <= (wordend + wordstart) / 2 ; ++j) {
      char temp = words[j];
      words[j] = words[wordend - (j - wordstart)];
      words[wordend - (j - wordstart)] = temp;
    }
    i = wordend;
  }
}