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

J'ai résolu le problème sans utiliser d'espace supplémentaire en utilisant uniquement la chaîne originale elle-même, mais je n'ai pas pu résoudre le problème en O(n), le moins que je puisse obtenir est O(n carré), et ce pour le pire des scénarios.

La façon dont j'ai mis en œuvre -

1. Inversez toute la phrase, caractère par caractère.
2. Plus tard, itérez la phrase entière mais cette fois-ci, inversez chaque mot.

ET C'EST POURQUOI J'AI OBTENU LA PLUS GRANDE COMPLEXITÉ EN TEMPS QU'O(n sqaure)

Veuillez trouver le code ci-dessous en java, j'espère que cela aidera quelqu'un.

class MainClass {
    public static void main(String args[]) {

        String str = "reverse me! also lets check";
        System.out.println("The initial string is  --->> " + str);

        for (int i = 0; i < str.length(); i++) {
            //Keep iterating each letter from one end to another.
            str = str.substring(1, str.length() - i)
                + str.substring(0, 1)
                + str.substring(str.length() - i, str.length());
        }
        System.out.println("The reversed string is ---->> " + str);

        for (int i = 0, j = 0; i < str.length(); i++) {
            if(str.charAt(i) == ' ' || i == (str.length() - 1)) {
                //Just to know the start of each word
                int k = j;

                //the below if condition is for considering the last word.
                if(i == (str.length() - 1)) i++;

                while(j < i) {
                    j++;
                    str = str.substring(0, k)
                        //(i-j) is the length of each word
                        + str.substring(k + 1, (k + 1) + i - j)
                        + str.substring(k, k + 1)
                        + str.substring((k + 1) + i - j, i)
                        + str.substring(i);
                    if(j == i) {
                        //Extra j++ for considering the empty white space
                        j++;
                    }
                }
            }
        }
        System.out.println("The reversed string but not the reversed words is ---->> " + str);

    }
}

Answer 2

Voici comment le faire dans Excel en tant qu'UDF et en VBA :

Public Function ReverseMe(textToReverse As String, _
          Optional delim As String = " ") As String

    Dim test    As String
    Dim arr     As Variant
    Dim arr2    As Variant
    Dim arrPart As Variant
    Dim cnt     As Long

    arr = Split(textToReverse, ".")
    ReDim arr2(UBound(arr))

    For Each arrPart In arr
        arr2(cnt) = StrReverse(arrPart)
        cnt = cnt + 1
    Next arrPart

    ReverseMe = StrReverse(Join(arr2, "."))

End Function

Public Sub TestMe()

    Debug.Print ReverseMe("veso.dosev.diri.rid", ".")
    Debug.Print ReverseMe("VBA is the best language")

End Sub

Answer 3

Cette question est posée lors d'un entretien avec Paytm pour le poste de Java. J'ai trouvé la solution suivante.

class ReverseStringWord{
public static void main(String[] args) {
    String s="My name is X Y Z";
    StringBuilder result=new StringBuilder();
    StringBuilder str=new StringBuilder();
    for(int i=0;i<s.length();i++){
        if(s.charAt(i)==' '){
            result.insert(0,str+" ");
            str.setLength(0);
        }
        else{
            str.append(s.charAt(i));
            if(i==s.length()-1){
                result.insert(0,str+" ");
            }
        }
    }
    System.out.println(result);
}}

Answer 4

En effectuant une rotation de la chaîne, vous pouvez inverser l'ordre des mots sans inverser l'ordre des lettres.

À mesure que chaque mot est tourné vers la fin de la chaîne, nous réduisons la quantité de la chaîne à tourner de la longueur du mot. Nous faisons ensuite tourner les espaces devant le mot que nous venons de placer à la fin de la chaîne et nous raccourcissons la partie de la chaîne qui tourne de 1 pour chaque espace. Si la chaîne entière est tournée sans voir un espace, nous avons terminé.

Voici une implémentation en C+. Le site l contient la longueur de la variable buf pour tourner, et n compte le nombre de rotations effectuées.

    #include <stdio.h>
    #include <string.h>

    int main(char *argv[], int argc)
    {
      char buf[20] = "My name is X Y Z";
      int l = strlen(buf);
      int n = 1;

      while (l >= n) {
        unsigned char c = buf[0];
        for (int i = 1; i < l; i++) {
          buf[i-1] = buf[i];
        }
        buf[l - 1] = c;
        if (buf[0] == ' ' || c == ' ') {
          l -= n;
          n = 1;
        } else {
          n++;
        }
      }

      printf("%s\n", buf);
    }

Le code de rotation a été volontairement laissé très simple.

Answer 5

En fait, la première réponse :

words = aString.split(" ");
for (i = 0; i < words.length; i++) {
    words[i] = words[words.length-i];
}

ne fonctionne pas car il annule dans la seconde moitié de la boucle le travail effectué dans la première moitié. Donc, i < words.length/2 fonctionnerait, mais un exemple plus clair est celui-ci :

words = aString.split(" "); // make up a list
i = 0; j = words.length - 1; // find the first and last elements
while (i < j) {
    temp = words[i]; words[i] = words[j]; words[j] = temp; //i.e. swap the elements
    i++; 
    j--;
}

Note : Je ne suis pas familier avec la syntaxe de PHP, et j'ai deviné la syntaxe de l'incrémenteur et du décrémenteur puisqu'elle semble être similaire à celle de Perl.