Revertir de manera eficiente el orden de las palabras (no los caracteres) en una matriz de caracteres

Dado un conjunto de caracteres que forman una oración de palabras, proporcione un algoritmo eficiente para invertir el orden de las palabras (no los caracteres) en él.

Ejemplo de entrada y salida:

>>> reverse_words("this is a string") 'string a is this' 

Debería ser el tiempo O (N) y el espacio O (1) ( split() y empujar / estallar fuera de la stack no están permitidos).

El rompecabezas está tomado de aquí .

Una solución en C / C ++:

 void swap(char* str, int i, int j){ char t = str[i]; str[i] = str[j]; str[j] = t; } void reverse_string(char* str, int length){ for(int i=0; i 

Esto debería ser O (n) en el tiempo y O (1) en el espacio.

Editar: lo limpié un poco.

El primer paso sobre la cadena es obviamente O (n / 2) = O (n). El segundo pase es O (n + longitud combinada de todas las palabras / 2) = O (n + n / 2) = O (n), lo que lo convierte en un algoritmo O (n).

empujar una cuerda en una stack y luego soltarla, ¿sigue siendo O (1)? esencialmente, eso es lo mismo que usar split () …

¿O (1) no significa en el lugar? Esta tarea es más fácil si solo podemos agregar cadenas y otras cosas, pero eso usa espacio …

EDITAR : Thomas Watnedal tiene razón. El siguiente algoritmo es O (n) en el tiempo y O (1) en el espacio:

  1. cadena inversa en el lugar (primera iteración sobre la cadena)
  2. revertir cada palabra (invertida) in situ (otras dos iteraciones sobre la cadena)
    1. encontrar el límite de la primera palabra
    2. revertir dentro de este límite de palabra
    3. repita para la próxima palabra hasta que termine

Creo que deberíamos probar que el paso 2 es realmente solo O (2n) …

 #include  #include  void reverse(std::string& foo) { using namespace std; std::reverse(foo.begin(), foo.end()); string::iterator begin = foo.begin(); while (1) { string::iterator space = find(begin, foo.end(), ' '); std::reverse(begin, space); begin = boost::next(space); if (space == foo.end()) break; } } 

Aquí está mi respuesta. No hay llamadas a la biblioteca ni estructuras de datos temporales.

 #include  void reverse(char* string, int length){ int i; for (i = 0; i < length/2; i++){ string[length - 1 - i] ^= string[i] ; string[i] ^= string[length - 1 - i]; string[length - 1 - i] ^= string[i]; } } int main () { char string[] = "This is a test string"; char *ptr; int i = 0; int word = 0; ptr = (char *)&string; printf("%s\n", string); int length=0; while (*ptr++){ ++length; } reverse(string, length); printf("%s\n", string); for (i=0;i 

En pseudo código:

 reverse input string reverse each word (you will need to find word boundaries) 

@Daren Thomas

Implementación de su algoritmo (O (N) en el tiempo, O (1) en el espacio) en D (Marte digital):

 #!/usr/bin/dmd -run /** * to compile & run: * $ dmd -run reverse_words.d * to optimize: * $ dmd -O -inline -release reverse_words.d */ import std.algorithm: reverse; import std.stdio: writeln; import std.string: find; void reverse_words(char[] str) { // reverse whole string reverse(str); // reverse each word for (auto i = 0; (i = find(str, " ")) != -1; str = str[i + 1..length]) reverse(str[0..i]); // reverse last word reverse(str); } void main() { char[] str = cast(char[])("this is a string"); writeln(str); reverse_words(str); writeln(str); } 

Salida:

  esto es una cadena
 una cuerda es esto 

en Ruby

“esto es una cadena” .split.reverse.join (“”)

En C: (C99)

 #include  #include  void reverseString(char* string, int length) { char swap; for (int i = 0; i < length/2; i++) { swap = string[length - 1 - i]; string[length - 1 - i] = string[i]; string[i] = swap; } } int main (int argc, const char * argv[]) { char teststring[] = "Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it."; printf("%s\n", teststring); int length = strlen(teststring); reverseString(teststring, length); int i = 0; while (i < length) { int wordlength = strspn(teststring + i, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"); reverseString(teststring + i, wordlength); i += wordlength + 1; } printf("%s\n", teststring); return 0; } 

Esto da salida:

Dado un conjunto de caracteres que forman una oración de palabras, proporcione un algoritmo eficiente para invertir el orden de las palabras (no los caracteres) en él.

.it in) caracteres no (palabras del orden inverso al algoritmo eficiente y un dado, palabras de la oración una forma que caracteres de matriz y dado

Esto toma como mucho 4N veces, con un pequeño espacio constante. Desafortunadamente, no maneja la puntuación o el caso con gracia.

O (N) en el espacio y O (N) en solución de tiempo en Python:

 def reverse_words_nosplit(str_): """ >>> f = reverse_words_nosplit >>> f("this is a string") 'string a is this' """ iend = len(str_) s = "" while True: ispace = str_.rfind(" ", 0, iend) if ispace == -1: s += str_[:iend] break s += str_[ispace+1:iend] s += " " iend = ispace return s 

Utilizaría lo que se conoce como una función recursiva iterativa, que es O (N) en el tiempo, ya que requiere N (N es el número de palabras) iteraciones para completar y O (1) en el espacio ya que cada iteración mantiene su propio estado dentro los argumentos de la función.

 (define (reverse sentence-to-reverse) (reverse-iter (sentence-to-reverse "")) (define (reverse-iter(sentence, reverse-sentence) (if (= 0 string-length sentence) reverse-sentence ( reverse-iter( remove-first-word(sentence), add-first-word(sentence, reverse-sentence))) 

Nota: He escrito esto en el esquema que soy un novato completo, así que me disculpo por la falta de manipulación correcta de la secuencia.

remove-first-word encuentra la primera palabra límite de la oración, luego toma esa sección de caracteres (incluyendo espacio y puntuación) y la elimina y devuelve una nueva oración

add-first-word encuentra la primera palabra límite de la oración, luego toma esa sección de caracteres (incluyendo espacio y puntuación) y la agrega a la oración inversa y devuelve nuevos contenidos de oraciones inversas.

ESTE PROGRAMA ES INVALIDAR LA ORACIÓN MEDIANTE EL USO DE INDICADORES EN “C”. Por Vasantha kumar y Sundaramoorthy de KONGU ENGG COLLEGE, Erode.

NOTA : la oración debe terminar con punto (.) Porque el carácter NULL no se asigna automáticamente al final de la oración *

  #include #include int main() { char *p,*s="this is good.",*t; int i,j,a,l,count=0; l=strlen(s); p=&s[l-1]; t=&s[-1]; while(*t) { if(*t==' ') count++; t++; } a=count; while(l!=0) { for(i=0;*p!=' '&&t!=p;p--,i++); p++; for(;((*p)!='.')&&(*p!=' ');p++) printf("%c",*p); printf(" "); if(a==count) { p=pi-1; l=li; } else { p=pi-2; l=li-1; } count--; } return 0; } 

Presione cada palabra en una stack. Pop todas las palabras de la stack.

 using System; namespace q47407 { class MainClass { public static void Main(string[] args) { string s = Console.ReadLine(); string[] r = s.Split(' '); for(int i = r.Length-1 ; i >= 0; i--) Console.Write(r[i] + " "); Console.WriteLine(); } } } 

editar: supongo que debería leer toda la pregunta … continuar.

Eficiente en términos de mi tiempo: me llevó menos de 2 minutos escribir en REBOL:

 reverse_words: func [s [string!]] [form reverse parse s none] 

Pruébelo: reverse_words “this is a string” “string a is this”

Una solución de C ++:

 #include  #include  using namespace std; string revwords(string in) { string rev; int wordlen = 0; for (int i = in.length(); i >= 0; --i) { if (i == 0 || iswspace(in[i-1])) { if (wordlen) { for (int j = i; wordlen--; ) rev.push_back(in[j++]); wordlen = 0; } if (i > 0) rev.push_back(in[i-1]); } else ++wordlen; } return rev; } int main() { cout < < revwords("this is a sentence") << "." << endl; cout << revwords(" a sentence with extra spaces ") << "." << endl; return 0; } 

Una solución de Ruby.

 # Reverse all words in string def reverse_words(string) return string if string == '' reverse(string, 0, string.size - 1) bounds = next_word_bounds(string, 0) while bounds.all? { |b| b < string.size } reverse(string, bounds[:from], bounds[:to]) bounds = next_word_bounds(string, bounds[:to] + 1) end string end # Reverse a single word between indices "from" and "to" in "string" def reverse(s, from, to) half = (from - to) / 2 + 1 half.times do |i| s[from], s[to] = s[to], s[from] from, to = from.next, to.next end s end # Find the boundaries of the next word starting at index "from" def next_word_bounds(s, from) from = s.index(/\S/, from) || s.size to = s.index(/\s/, from + 1) || s.size return { from: from, to: to - 1 } end 

en C #, in situ, O (n), y probado:

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

Este problema se puede resolver con O (n) en el tiempo y O (1) en el espacio. El código de muestra se ve como se menciona a continuación:

  public static string reverseWords(String s) { char[] stringChar = s.ToCharArray(); int length = stringChar.Length, tempIndex = 0; Swap(stringChar, 0, length - 1); for (int i = 0; i < length; i++) { if (i == length-1) { Swap(stringChar, tempIndex, i); tempIndex = i + 1; } else if (stringChar[i] == ' ') { Swap(stringChar, tempIndex, i-1); tempIndex = i + 1; } } return new String(stringChar); } private static void Swap(char[] p, int startIndex, int endIndex) { while (startIndex < endIndex) { p[startIndex] ^= p[endIndex]; p[endIndex] ^= p[startIndex]; p[startIndex] ^= p[endIndex]; startIndex++; endIndex--; } } 

Algoritmo: 1). Resuelve cada palabra de la cadena. 2) .Rose resultante Cadena.

 public class Solution { public String reverseWords(String p) { String reg=" "; if(p==null||p.length()==0||p.equals("")) { return ""; } String[] a=p.split("\\s+"); StringBuilder res=new StringBuilder();; for(int i=0;i 

Un trazador de líneas uno:

 l="Is this as expected ??" " ".join(each[::-1] for each in l[::-1].split()) 

Salida:

 '?? expected as this Is' 

El algoritmo para resolver este problema se basa en el proceso de dos pasos, el primer paso invertirá las palabras individuales de la cadena, luego en el segundo paso, invertirá la secuencia completa. La implementación del algoritmo tendrá O (n) tiempo y O (1) complejidad del espacio.

  #include  #include  void reverseStr(char* s, int start, int end); int main() { char s[] = "This is test string"; int start = 0; int end = 0; int i = 0; while (1) { if (s[i] == ' ' || s[i] == '\0') { reverseStr(s, start, end-1); start = i + 1; end = start; } else{ end++; } if(s[i] == '\0'){ break; } i++; } reverseStr(s, 0, strlen(s)-1); printf("\n\noutput= %s\n\n", s); return 0; } void reverseStr(char* s, int start, int end) { char temp; int j = end; int i = start; for (i = start; i < j ; i++, j--) { temp = s[i]; s[i] = s[j]; s[j] = temp; } }