Invierta eficientemente el orden de las palabras (no de los caracteres) en una serie de caracteres

Question

Dada una serie de caracteres que forma una oración de palabras, proporcione un algoritmo eficiente para invertir el orden de las palabras (no de los caracteres) que contiene.

Ejemplo de entrada y salida:

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

Debería ser O(N) tiempo y O(1) espacio (split() y no se permite empujar o sacar la pila).

El rompecabezas está tomado de aquí.

Answer 1

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<length/2; i++){
        swap(str, i, length-i-1);
    }
}
void reverse_words(char* str){
    int l = strlen(str);
    //Reverse string
    reverse_string(str,strlen(str));
    int p=0;
    //Find word boundaries and reverse word by word
    for(int i=0; i<l; i++){
        if(str[i] == ' '){
            reverse_string(&str[p], i-p);
            p=i+1;
        }
    }
    //Finally reverse the last word.
    reverse_string(&str[p], l-p);
}

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 cuerda es obviamente O(n/2) = O(n).La segunda pasada 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).

Answer 2

empujar una cuerda a una pila y luego sacarla: ¿sigue siendo O (1)?Básicamente, eso es lo mismo que usar split()...

¿No significa O(1) en el lugar?Esta tarea se vuelve fácil si podemos simplemente agregar cadenas y demás, 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. invertir cada palabra (invertida) en el lugar (otras dos iteraciones sobre la cadena)
   1. encontrar el límite de la primera palabra
   2. invertir dentro de este límite de palabra
   3. repetir para la siguiente palabra hasta terminar

Supongo que necesitaríamos demostrar que el paso 2 es en realidad sólo O(2n)...

Answer 3

#include <string>
#include <boost/next_prior.hpp>

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

Answer 4

Aquí está mi respuesta.Sin llamadas a bibliotecas ni estructuras de datos temporales.

#include <stdio.h>

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<length;i++){
    if(string[i] == ' '){
       reverse(&string[word], i-word);
       word = i+1;
       }
}   
reverse(&string[word], i-word); //for last word             
printf("\n%s\n", string);
return 0;
}

Answer 5

En pseudocódigo:

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

Answer 6

@Daren Tomás

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

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

Producción:

this is a string
string a is this

Answer 7

en rubí

"esto es una cadena".split.reverse.join(" ")

Answer 8

Cª:(C99)

#include <stdio.h>
#include <string.h>

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:

Dada una serie de caracteres que forman una oración de palabras, dan un algoritmo eficiente para revertir el orden de las palabras (no caracteres) en ella.

.it en) caracteres no (palabras de ordenar el reverso al algoritmo eficiente y dar, palabras de oración una forma que caracteres de matriz un dado

Esto lleva como máximo 4N de tiempo, con un espacio constante pequeño.Desafortunadamente, no maneja correctamente la puntuación ni las mayúsculas y minúsculas.

Answer 9

Solución O(N) en el espacio y O(N) en el 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

Answer 10

Se utilizaría lo que se conoce como función recursiva iterativa, que es O(N) en el tiempo, ya que se necesitan N (siendo N el número de palabras) iteraciones para completarse y O(1) en el espacio, ya que cada iteración mantiene su propio estado dentro de 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 un esquema en el que soy un completo novato, así que me disculpo por la falta de manipulación correcta de las cadenas.

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

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

Answer 11

ESTE PROGRAMA ES PARA INVERTIR LA ORACIÓN USANDO PUNTEROS EN "lenguaje C" Por Vasantha kumar y Sundaramoorthy de KONGU ENGG COLLEGE, Erode.

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

 #include<stdio.h>
 #include<string.h>

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=p-i-1;
     l=l-i;
   }
  else
   {
     p=p-i-2;
     l=l-i-1;
   }

count--;
  }

return 0;  
}

Answer 12

Coloca cada palabra en una pila.Saca todas las palabras de la pila.

Answer 13

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 la pregunta completa...continuar.

Answer 14

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

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

Pruébalo:reverse_words "Esta es una cadena" "Cadena A es esta"

Answer 15

Una solución C++:

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

Answer 16

Una solución 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

Answer 17

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

Answer 18

Este problema se puede resolver con O(n) en el tiempo y O(1) en el espacio.El código de muestra tiene el aspecto que 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--;
        }
    }

Answer 19

Algoritmo:1).Invierte cada palabra de la cadena.2).Cadena resultante inversa.

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<a.length;i++)
{

    String temp=doReverseString(a[i]);
    res.append(temp);
    res.append(" ");
}
String resultant=doReverseString(res.toString());
System.out.println(res);
return resultant.toString().replaceAll("^\\s+|\\s+$", ""); 
}


public String doReverseString(String s)`{`


char str[]=s.toCharArray();
int start=0,end=s.length()-1;
while(start<end)
{
char temp=str[start];
str[start]=str[end];
str[end]=temp;
start++;
end--;
}
String a=new String(str);
return a;

}

public static void main(String[] args)
{
Solution r=new Solution();
String main=r.reverseWords("kya hua");
//System.out.println(re);
System.out.println(main);
}
}

Answer 20

Una sola línea:

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

Producción:

'?? expected as this Is'

Answer 21

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

      #include <stdio.h>
      #include <string.h>

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