algorithm - reves - invertir una cadena en dev c++

Invertir el orden de las palabras en una cadena

Question

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)?

Answer 1

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

Answer 2

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

Answer 3

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<len/2;i++) {
c = str[i];
str[i] = str[len-i-1];
str[len-i-1] = c;
}
return str;
}
char* inplace_reverse_words(char *w)
{
reverse(w); // reverse all letters first
bool is_word_start = (w[0]!=0x20);
for(size_t i=0;i<strlen(w);i++){
if(w[i]!=0x20 && is_word_start) {
reverse(&w[i], 0x20); // reverse one word only
is_word_start = false;
}
if (!is_word_start && w[i]==0x20) // found new word
is_word_start = true;
}
return w;
}

Answer 4

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<chars.length && i<=lastJ) {
iChar = chars[i];
if (iChar == SPACE) {
lengthI = i-lastI;
for (int j=lastJ; j>=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; i<length; i++) {
indexA = startA+i;
indexB = startB+i;
c = array[indexB];
array[indexB] = array[indexA];
array[indexA] = c;
}
if (lengthB>lengthA) {
length = lengthB-lengthA;
int end = 0;
for (int i=0; i<length; i++) {
end = endB-((length-1)-i);
c = array[end];
shiftRight(endA+i,end,array);
array[endA+1+i] = c;
}
} else if (lengthA>lengthB) {
length = lengthA-lengthB;
for (int i=0; i<length; i++) {
c = array[endA];
shiftLeft(endA,endB,array);
array[endB+i] = c;
}
}
}
private static final void shiftRight(int start, int end, char[] array) {
for (int i=end; i>start; i--) {
array[i] = array[i-1];
}
}
private static final void shiftLeft(int start, int end, char[] array) {
for (int i=start; i<end; i++) {
array[i] = array[i+1];
}
}

Answer 5

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]

Answer 6

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í.

Answer 7

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

#include<stdio.h>
#include<stdlib.h>
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<y)
{
y--;
char c=a[x];a[x]=a[y];a[y]=c;
x++;
}
x=z;
}
}
fprintf(stdout,a);
return 0;
}

Answer 8

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.length / 2 funcionaría, pero un ejemplo más claro es este:

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

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

Answer 9

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

#include <stdio.h>
#include <stdlib.h>
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");
}

Answer 10

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 pila local llamada buf para copiar todas las palabras y no puedo copiar sino en la cadena de origen, ya que esto provocaría un bloqueo si la cadena fuente es const char * type.

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

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

Answer 11

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

#include <stdio.h>
#include <string.h>
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;
}

Answer 12

Imprimir palabras en orden inverso de una declaración 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('' '');
}
}
}

Answer 13

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

Después del primer pase, la cuerda será

s1 = "Z Y X si eman yM"

y después del segundo pase será

s1 = "Z Y X is name My"

Answer 14

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 <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 15

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

Answer 16

Mi versión de usar stack:

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 17

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

Answer 18

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

void ReverseWords(char Arr[])
{
std::stack<std::string> 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();
}
}

Answer 19

Qué tal si ...

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

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

Answer 20

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<stdio.h>
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;
}

Answer 21

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<end)
{
char temp = s[start];
s[start] = s[end];
s[end]=temp;
start++;
end --;
}
}
void revertWords(char *s)
{
int start = 0;
char *temp = (char *)malloc(strlen(s) + 1);
int numCharacters = 0;
while(sscanf(&s[start], "%s", temp) !=EOF)
{
numCharacters = strlen(temp);
revertString(s, start, start+numCharacters -1);
start = start+numCharacters + 1;
if(s[start-1] == 0)
return;
}
free (temp);
}
void revertWordsInString(char *s)
{
revertString(s,0, strlen(s)-1);
revertWords(s);
}
int main()
{
char *s= new char [strlen("abc deff gh1 jkl")+1];
strcpy(s,"abc deff gh1 jkl");
revertWordsInString(s);
printf("%s",s);
return 0;
}

Answer 22

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. . .

Answer 23

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

Answer 24

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

Answer 25

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

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

Answer 26

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 27

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

Answer 28

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

}

Answer 29

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

Answer 30

public static String ReverseString(String str)
{
int word_length = 0;
String result = "";
for (int i=0; i<str.Length; i++)
{
if (str[i] == '' '')
{
result = " " + result;
word_length = 0;
} else
{
result = result.Insert(word_length, str[i].ToString());
word_length++;
}
}
return result;
}

Este es el código de C #.