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

La plupart de ces réponses ne tiennent pas compte des espaces avant et/ou arrière dans la chaîne d'entrée. Considérons le cas de str=" Hello world" ... L'algo simple qui consiste à inverser toute la chaîne et à inverser les mots individuels finit par inverser les délimiteurs, ce qui aboutit à f(str) == "world Hello " .

L'OP a dit "Je veux inverser l'ordre des mots" et n'a pas mentionné que les espaces de début et de fin devaient également être inversés ! Donc, bien qu'il y ait déjà une tonne de réponses, je vais en fournir une [espérons-le] plus correcte en C++ :

#include <string>
#include <algorithm>

void strReverseWords_inPlace(std::string &str)
{
  const char delim = ' ';
  std::string::iterator w_begin, w_end;
  if (str.size() == 0)
    return;

  w_begin = str.begin();
  w_end   = str.begin();

  while (w_begin != str.end()) {
    if (w_end == str.end() || *w_end == delim) {
      if (w_begin != w_end)
        std::reverse(w_begin, w_end);
      if (w_end == str.end())
        break;
      else
        w_begin = ++w_end;
    } else {
      ++w_end;
    }
  }

  // instead of reversing str.begin() to str.end(), use two iterators that
  // ...represent the *logical* begin and end, ignoring leading/traling delims
  std::string::iterator str_begin = str.begin(), str_end = str.end();
  while (str_begin != str_end && *str_begin == delim)
    ++str_begin;
  --str_end;
  while (str_end != str_begin && *str_end == delim)
    --str_end;
  ++str_end;
  std::reverse(str_begin, str_end);
}

Answer 2

Ma version de l'utilisation de la pile :

public class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        String ns= s.trim();
        Stack<Character> reverse = new Stack<Character>();
        boolean hadspace=false;

        //first pass
        for (int i=0; i< ns.length();i++){
            char c = ns.charAt(i);
            if (c==' '){
                if (!hadspace){
                    reverse.push(c);
                    hadspace=true;
                }
            }else{
                hadspace=false;
                reverse.push(c);
            }
        }
        Stack<Character> t = new Stack<Character>();
        while (!reverse.empty()){
            char temp =reverse.pop();
            if(temp==' '){
                //get the stack content out append to StringBuilder
                while (!t.empty()){
                    char c =t.pop();
                    sb.append(c);
                }
                sb.append(' ');
            }else{
                //push to stack
                t.push(temp);
            }
        }
        while (!t.empty()){
            char c =t.pop();
            sb.append(c);
        }
        return sb.toString();
    }
}

Answer 3

Stocker chaque mot comme une chaîne de caractères dans le tableau puis imprimer à partir de la fin.

public void rev2() {
    String str = "my name is ABCD";
    String A[] = str.split(" ");

    for (int i = A.length - 1; i >= 0; i--) {
        if (i != 0) {
            System.out.print(A[i] + " ");
        } else {
            System.out.print(A[i]);
        }
    }

}

Answer 4

En Python, si vous ne pouvez pas utiliser [::-1] ou reversed(), voici la méthode simple :

def reverse(text):

  r_text = text.split(" ")
  res = []
  for word in range(len(r_text) - 1, -1, -1): 
    res.append(r_text[word])

  return " ".join(res)

print (reverse("Hello World"))

>> World Hello
[Finished in 0.1s]

Answer 5

Impression des mots dans l'ordre inverse d'une déclaration donnée en utilisant C# :

    void ReverseWords(string str)
    {
        int j = 0;
        for (int i = (str.Length - 1); i >= 0; i--)
        {
            if (str[i] == ' ' || i == 0)
            {
                j = i == 0 ? i : i + 1;

                while (j < str.Length && str[j] != ' ')
                    Console.Write(str[j++]);
                Console.Write(' ');
            }
        }
    }