Reverter a ordenação de palavras em uma string

Eu tenho essa string s1 = "My name is XYZ" e eu quero inverter a ordem das palavras para que s1 = "ZYX is name My" .

Eu posso fazer isso usando uma matriz adicional. Eu pensei muito, mas é possível fazer isso no local (sem usar estruturas de dados adicionais) e com a complexidade de tempo sendo O (n)?

Inverta a string inteira e, em seguida, inverta as letras de cada palavra individual.

Após a primeira passagem, a string será

 s1 = "ZYX si eman yM" 

e depois da segunda passagem será

 s1 = "ZYX is name My" 

inverta a corda e depois, em uma segunda passagem, inverta cada palavra …

em c #, completamente no local sem matrizes adicionais:

 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' 

Em Smalltalk:

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

Eu sei que ninguém se importa com o Smalltalk, mas é tão bonito para mim.

Você não pode fazer a reversão sem pelo menos alguma estrutura de dados extra. Eu acho que a menor estrutura seria um único caractere como um buffer enquanto você troca letras. Ele ainda pode ser considerado “in loco”, mas não é completamente “extra estrutura livre de dados”.

Abaixo está o código de implementação do que Bill the Lizard descreve:

 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 lingua? Se PHP, você pode explodir no espaço e passar o resultado para array_reverse.

Se não for PHP, você terá que fazer algo um pouco mais complexo 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 é o código C #.

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

De qualquer forma cookamunga fornecida boa solução inline usando python!

Isto está assumindo que todas as palavras estão separadas por espaços:

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

Isso não é perfeito, mas funciona para mim agora. Eu não sei se tem O (n) tempo de execução btw (ainda estudando isso ^^), mas ele usa uma matriz adicional para cumprir a tarefa.

Provavelmente não é a melhor resposta para o seu problema, porque eu uso uma string de destino para salvar a versão invertida em vez de replace cada palavra na string de origem. O problema é que eu uso uma variável de pilha local chamada buf para copiar todas as palavras e não posso copiar, mas na cadeia de origem, pois isso levaria a uma falha se a cadeia de origem é const char * type.

Mas foi minha primeira tentativa de escrever s.th. assim 🙂 Ok o suficiente blablub. aqui está o 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 inserir a string em uma pilha e quando extrairmos as palavras, elas estarão na ordem inversa.

 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 programa rápido funciona … mas não verifica os casos de canto.

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

A maioria dessas respostas não leva em conta espaços iniciais e / ou finais na cadeia de input. Considere o caso de str=" Hello world" … O simples algo de inverter toda a string e inverter palavras individuais acaba por inverter os delimitadores, resultando em f(str) == "world Hello " .

O OP disse “Quero reverter a ordem das palavras” e não mencionou que os espaços iniciais e finais também devem ser invertidos! Portanto, embora haja uma tonelada de respostas, fornecerei um [mais esperançosamente] mais correto em 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); } 

Minha versão do uso de pilha:

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

Armazenar Cada palavra como uma string no array e depois imprimir do 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]); } } } 

Em Python, se você não pode usar [:: – 1] ou invertido (), aqui está a maneira mais simples:

 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] 

Imprimindo palavras na ordem inversa de uma determinada instrução 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(' '); } } } 

Na verdade, a primeira resposta:

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

não funciona porque desfaz na segunda metade do loop o trabalho que fez no primeiro semestre. Então, eu

 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: Eu não estou familiarizado com a syntax do PHP, e adivinhei a syntax do incrementador e do decrementador, uma vez que parece ser semelhante ao Perl.

E se …

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

Eu acho que não está em linha tho.

Em c, é assim que você pode fazer isso, O (N) e somente usando estruturas de dados O (1) (isto é, um 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 

Pode ser feito mais simples usando o 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]); } } 

}

Em Java usando uma String adicional (com 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(); } 

Em Java in-place:

 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 

Aqui está uma implementação C que está fazendo a palavra inverter inlace, e tem complexidade O(n) .

 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 

Solução c # para reverter palavras em uma frase

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

saída: peaople do coração o em mentiras beleza Pressione qualquer tecla para continuar. . .

Melhor versão
Veja meu 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); } 

Eu sei que existem várias respostas corretas. Aqui está o em C que eu inventei. Esta é uma implementação da resposta com exceção. A complexidade do tempo é O (n) e nenhuma string extra é usada.

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