Invertir el orden de las palabras en una cadena

Tengo esta string s1 = "My name is XYZ" y quiero invertir el orden de las palabras para que s1 = "ZYX is name My" .

Puedo hacerlo usando una matriz adicional. Pensé mucho pero ¿es posible hacerlo en el lugar (sin usar estructuras de datos adicionales) y con la complejidad del tiempo siendo O (n)?

Invierta la secuencia completa, luego invierta las letras de cada palabra individual.

Después del primer pase, la cuerda será

 s1 = "ZYX si eman yM" 

y después del segundo pase será

 s1 = "ZYX is name My" 

invierta la cuerda y luego, en una segunda pasada, invierta cada palabra …

en c #, completamente in situ sin matrices adicionales:

 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; } 
 Not exactly in place, but anyway: Python: >>> a = "These pretzels are making me thirsty" >>> " ".join(a.split()[::-1]) 'thirsty me making are pretzels These' 

En Smalltalk:

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

Sé que a nadie le importa Smalltalk, pero es tan hermoso para mí.

No puede hacer la inversión sin al menos alguna estructura de datos adicional. Creo que la estructura más pequeña sería un solo carácter como un buffer mientras intercambias letras. Todavía se puede considerar “in situ”, pero no es completamente “estructura de datos extra gratuita”.

A continuación se muestra el código que implementa lo que Bill the Lizard describe:

 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; } } 

¿Que lenguaje? Si PHP, puede explotar en el espacio, luego pasar el resultado a array_reverse.

Si no es PHP, tendrás que hacer algo un poco más complejo como:

 words = aString.split(" "); for (i = 0; i < words.length; i++) { words[i] = words[words.length-i]; } 
 public static String ReverseString(String str) { int word_length = 0; String result = ""; for (int i=0; i 

Este es el código de C #.

 In Python... ip = "My name is XYZ" words = ip.split() words.reverse() print ' '.join(words) 

De todos modos, ¡cookamunga proporcionó una buena solución en línea usando Python!

Esto supone que todas las palabras están separadas por espacios:

 #include  #include  int main() { char string[] = "What are you looking at"; int i, n = strlen(string); int tail = n-1; for(i=n-1;i>=0;i--) { if(string[i] == ' ' || i == 0) { int cursor = (i==0? i: i+1); while(cursor <= tail) printf("%c", string[cursor++]); printf(" "); tail = i-1; } } return 0; } 
 class Program { static void Main(string[] args) { string s1 =" My Name varma:; string[] arr = s1.Split(' '); Array.Reverse(arr); string str = string.Join(" ", arr); Console.WriteLine(str); Console.ReadLine(); } } 

Esto no es perfecto, pero funciona para mí en este momento. No sé si tiene O (n) tiempo de ejecución por cierto (todavía lo está estudiando ^^) pero usa una matriz adicional para completar la tarea.

Probablemente no sea la mejor respuesta a su problema porque utilizo una cadena de destino para guardar la versión invertida en lugar de reemplazar cada palabra en la cadena fuente. El problema es que utilizo una variable de stack local llamada buf para copiar todas las palabras y no puedo copiar sino en la cadena de origen, ya que esto provocaría un locking si la cadena fuente es const char * type.

Pero fue mi primer bash de escribir en el s.th. como este 🙂 Ok suficiente blablub. aquí está el código:

 #include  using namespace std; void reverse(char *des, char * const s); int main (int argc, const char * argv[]) { char* s = (char*)"reservered. rights All Saints. The 2011 (c) Copyright 11/10/11 on Pfundstein Markus by Created"; char *x = (char*)"Dogfish! White-spotted Shark, Bullhead"; printf("Before: |%s|\n", x); printf("Before: |%s|\n", s); char *d = (char*)malloc((strlen(s)+1)*sizeof(char)); char *i = (char*)malloc((strlen(x)+1)*sizeof(char)); reverse(d,s); reverse(i,x); printf("After: |%s|\n", i); printf("After: |%s|\n", d); free (i); free (d); return 0; } void reverse(char *dest, char *const s) { // create a temporary pointer if (strlen(s)==0) return; unsigned long offset = strlen(s)+1; char *buf = (char*)malloc((offset)*sizeof(char)); memset(buf, 0, offset); char *p; // iterate from end to begin and count how much words we have for (unsigned long i = offset; i != 0; i--) { p = s+i; // if we discover a whitespace we know that we have a whole word if (*p == ' ' || *p == '\0') { // we increment the counter if (*p != '\0') { // we write the word into the buffer ++p; int d = (int)(strlen(p)-strlen(buf)); strncat(buf, p, d); strcat(buf, " "); } } } // copy the last word p -= 1; int d = (int)(strlen(p)-strlen(buf)); strncat(buf, p, d); strcat(buf, "\0"); // copy stuff to destination string for (int i = 0; i < offset; ++i) { *(dest+i)=*(buf+i); } free(buf); } 

Podemos insertar la cadena en una stack y cuando extraemos las palabras, estarán en orden inverso.

 void ReverseWords(char Arr[]) { std::stack s; char *str; int length = strlen(Arr); str = new char[length+1]; std::string ReversedArr; str = strtok(Arr," "); while(str!= NULL) { s.push(str); str = strtok(NULL," "); } while(!s.empty()) { ReversedArr = s.top(); cout << " " << ReversedArr; s.pop(); } } 

Este rápido progtwig funciona … pero no revisa los casos de las esquinas.

 #include  #include  struct node { char word[50]; struct node *next; }; struct stack { struct node *top; }; void print (struct stack *stk); void func (struct stack **stk, char *str); main() { struct stack *stk = NULL; char string[500] = "the sun is yellow and the sky is blue"; printf("\n%s\n", string); func (&stk, string); print (stk); } void func (struct stack **stk, char *str) { char *p1 = str; struct node *new = NULL, *list = NULL; int i, j; if (*stk == NULL) { *stk = (struct stack*)malloc(sizeof(struct stack)); if (*stk == NULL) printf("\n####### stack is not allocated #####\n"); (*stk)->top = NULL; } i = 0; while (*(p1+i) != '\0') { if (*(p1+i) != ' ') { new = (struct node*)malloc(sizeof(struct node)); if (new == NULL) printf("\n####### new is not allocated #####\n"); j = 0; while (*(p1+i) != ' ' && *(p1+i) != '\0') { new->word[j] = *(p1 + i); i++; j++; } new->word[j++] = ' '; new->word[j] = '\0'; new->next = (*stk)->top; (*stk)->top = new; } i++; } } void print (struct stack *stk) { struct node *tmp = stk->top; int i; while (tmp != NULL) { i = 0; while (tmp->word[i] != '\0') { printf ("%c" , tmp->word[i]); i++; } tmp = tmp->next; } printf("\n"); } 

La mayoría de estas respuestas no tienen en cuenta los espacios iniciales y / o finales en la cadena de entrada. Considere el caso de str=" Hello world" … El simple algo de invertir toda la cadena e invertir palabras individuales termina volteando delimitadores resultando en f(str) == "world Hello " .

El OP dijo “¡Quiero invertir el orden de las palabras” y no mencionó que los espacios iniciales y finales también deben ser volteados! Entonces, aunque ya hay un montón de respuestas, proporcionaré una [afortunadamente] más correcta en C ++:

 #include  #include  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); } 

Mi versión de usar stack:

 public class Solution { public String reverseWords(String s) { StringBuilder sb = new StringBuilder(); String ns= s.trim(); Stack reverse = new Stack(); 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 t = new Stack(); 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(); } } 

Almacene cada palabra como una cadena en una matriz y luego imprima desde el final

 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]); } } } 

En Python, si no puede usar [:: – 1] o invertir (), aquí está la manera 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] 

Imprimir palabras en orden inverso de una statement dada usando 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(' '); } } } 

En realidad, la primera respuesta:

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

no funciona porque deshace en la segunda mitad del ciclo el trabajo que hizo en la primera mitad. Entonces, i

 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; //ie swap the elements i++; j--; } 

Nota: No estoy familiarizado con la syntax PHP, y he adivinado la syntax de incremento y decremento ya que parece ser similar a Perl.

Qué tal si …

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

Supongo que eso no está en línea aunque.

En c, así es como lo puedes hacer, O (N) y solo usando O (1) estructuras de datos (es decir, un char).

 #include #include 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 

Se puede hacer de manera más simple usando 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 
 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]); } } 

}

En Java usando un String adicional (con 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 situ:

 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=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; ilengthA) { length = lengthB-lengthA; int end = 0; for (int i=0; ilengthB) { length = lengthA-lengthB; for (int i=0; istart; i--) { array[i] = array[i-1]; } } private static final void shiftLeft(int start, int end, char[] array) { for (int i=start; i 

Aquí hay una implementación C que está haciendo la palabra Invertir Inlace, y tiene O(n) complejidad.

 char* reverse(char *str, char wordend=0) { char c; size_t len = 0; if (wordend==0) { len = strlen(str); } else { for(size_t i=0;str[i]!=wordend && str[i]!=0;i++) len = i+1; } for(size_t i=0;i 

Solución de c # para invertir palabras en una oración

 using System; class helloworld { public void ReverseString(String[] words) { int end = words.Length-1; for (int start = 0; start < end; start++) { String tempc; if (start < end ) { tempc = words[start]; words[start] = words[end]; words[end--] = tempc; } } foreach (String s1 in words) { Console.Write("{0} ",s1); } } } class reverse { static void Main() { string s= "beauty lies in the heart of the peaople"; String[] sent_char=s.Split(' '); helloworld h1 = new helloworld(); h1.ReverseString(sent_char); } } 

salida: gente del corazón la belleza de mentiras Presione cualquier tecla para continuar. . .

Mejor versión
Mira mi blog http://bamaracoulibaly.blogspot.co.uk/2012/04/19-reverse-order-of-words-in-text.html

 public string reverseTheWords(string description) { if(!(string.IsNullOrEmpty(description)) && (description.IndexOf(" ") > 1)) { string[] words= description.Split(' '); Array.Reverse(words); foreach (string word in words) { string phrase = string.Join(" ", words); Console.WriteLine(phrase); } return phrase; } return description; } 
 public class manip{ public static char[] rev(char[] a,int left,int right) { char temp; for (int i=0;i<(right - left)/2;i++) { temp = a[i + left]; a[i + left] = a[right -i -1]; a[right -i -1] = temp; } return a; } public static void main(String[] args) throws IOException { String s= "i think this works"; char[] str = s.toCharArray(); int i=0; rev(str,i,s.length()); int j=0; while(j < str.length) { if (str[j] != ' ' && j != str.length -1) { j++; } else { if (j == (str.length -1)) { j++; } rev(str,i,j); i=j+1; j=i; } } System.out.println(str); } 

Sé que hay varias respuestas correctas. Aquí está el de C que se me ocurrió. Esta es una implementación de la respuesta exceptuada. La complejidad del tiempo es O (n) y no se utiliza ninguna cadena adicional.

 #include char * strRev(char *str, char tok) { int len = 0, i; char *temp = str; char swap; while(*temp != tok && *temp != '\0') { len++; temp++; } len--; for(i = 0; i < len/2; i++) { swap = str[i]; str[i] = str[len - i]; str[len - i] = swap; } // Return pointer to the next token. return str + len + 1; } int main(void) { char a[] = "Reverse this string."; char *temp = a; if (a == NULL) return -1; // Reverse whole string character by character. strRev(a, '\0'); // Reverse every word in the string again. while(1) { temp = strRev(temp, ' '); if (*temp == '\0') break; temp++; } printf("Reversed string: %s\n", a); return 0; } 

Uso

 char str[50] = {0}; strcpy(str, (char*)"My name is Khan"); reverseWords(str); 

Método

 void reverseWords(char* pString){ if(NULL ==pString){ return; } int nLen = strlen(pString); reverseString(pString,nLen); char* start = pString; char* end = pString; nLen = 0; while (*end) { if(*end == ' ' ){ reverseString(start,nLen); end++; start = end; nLen = 0; continue; } nLen++; end++; } reverseString(start,nLen); printf("\n Reversed: %s",pString); } void reverseString(char* start,int nLen){ char* end = start+ nLen-1; while(nLen > 0){ char temp = *start; *start = *end; *end = temp; end--; start++; nLen-=2; } }