Reverse Words in a String

Q: ¿Cuál es la complejidad temporal de Invertir palabras en una cadena?

Ambos enfoques se ejecutan en tiempo O(n) para una cadena de longitud n , porque cada carácter se lee y se escribe una cantidad constante de veces. La división utiliza espacio adicional O(n) para la lista de palabras. Invertir la cadena completa y después cada palabra requiere espacio adicional O(1) en un arreglo de caracteres que puedes modificar.

MedioArrays y cadenas Dos punteros

+10

Recibes una cadena s formada por palabras y espacios. Una palabra es una secuencia de letras y dígitos sin espacios en su interior. Las palabras pueden estar separadas por más de un espacio, y s puede empezar o terminar con espacios.

Devuelve las palabras en orden inverso, unidas por exactamente un espacio, sin espacios al principio ni al final. Cada palabra conserva su escritura; solo cambia el orden de las palabras.

Función

reverseWords(s: string) → string

sstring: letras, dígitos y espacios que contienen al menos una palabra
Devuelvestring: las palabras de s en orden inverso, separadas por espacios individuales

Restricciones

1 ≤ s.length ≤ 10⁴
s contiene solo letras, dígitos y espacios en inglés.
s contiene al menos una palabra.

Ejemplos

Entrada: s = "Coddy runs in 15 languages"
Salida: "languages 15 in runs Coddy"
Explicación: Las palabras son Coddy, runs, in, 15 y languages. Leídas de la última a la primera, dan languages 15 in runs Coddy; 15 cuenta como una palabra porque las palabras pueden contener dígitos.

Entrada: s = " practice makes progress "
Salida: "progress makes practice"
Explicación: Se eliminan los espacios de ambos extremos, y las secuencias de dos y tres espacios entre las palabras se reducen a uno. Las tres palabras aparecen de la última a la primera: progress makes practice.

Entrada: s = " single "
Salida: "single"
Explicación: Una lista de una palabra se lee igual al revés. Solo se eliminan los espacios alrededor, así que la respuesta es single.

Para ir más allá

¿Puedes invertir las palabras, pero mantener los espacios de s: las mismas secuencias de espacios, con las mismas longitudes y en el mismo orden?

Solución

El orden de las palabras es una inversión; los espacios son donde fallan las soluciones. Los espacios al principio o al final y los espacios repetidos entre palabras deben desaparecer, y debe quedar exactamente un espacio entre las palabras en la respuesta. Puedes dividir la cadena en una lista de palabras, o invertir toda la cadena y luego cada palabra dentro de un arreglo.

Divídelas en palabras y únelas en orden inverso

Intuición

Divide s en sus palabras, invierte la lista y únela con espacios simples. La división requiere cuidado: dividir " practice makes progress " en cada espacio individual produce seis elementos vacíos alrededor de las tres palabras. Elimina los elementos vacíos y la lista queda como practice, makes, progress.

La división lee cada carácter una vez y la unión escribe cada carácter conservado una vez, así que el tiempo es O(n) para una cadena de longitud n. La lista de palabras y la respuesta ocupan O(n) de espacio adicional.

Algoritmo

Divide s por los espacios.
Elimina las partes vacías.
Invierte la lista de palabras.
Une las palabras con un espacio entre cada una y devuelve el resultado.

def reverseWords(s):
    # split() with no argument treats any run of spaces as one separator
    # and ignores spaces at both ends.
    words = s.split()
    words.reverse()
    return " ".join(words)

Invierte toda la cadena y después cada palabra

Intuición

Invertir toda la cadena pone las palabras en el orden correcto, pero escribe cada una al revés: Coddy runs in 15 languages se convierte en segaugnal 51 ni snur yddoC. Invertir después cada palabra por separado da languages 15 in runs Coddy.

Los espacios se procesan en la misma pasada. Un índice read recorre el arreglo invertido y omite los espacios; un índice write marca dónde va el siguiente carácter que se conserva. Copiar nunca sobrescribe un carácter que aún necesitas, porque write nunca pasa de read: el espacio que se escribe antes de una palabra ocupa el lugar de al menos un espacio que read omitió.

Cada carácter se copia como máximo una vez y se intercambia como máximo dos veces, así que el tiempo es O(n), con espacio adicional O(1) en un búfer de caracteres que puedes modificar. Aquí las cadenas llegan como valores, así que cada solución crea una copia de trabajo de s: O(n) de memoria en total.

Algoritmo

Copia s en un arreglo de caracteres e invierte todo el arreglo.
Recorre el arreglo con un índice de lectura y omite los espacios.
En cada palabra, escribe primero un espacio, a menos que sea la primera palabra; después, copia los caracteres de la palabra en el índice de escritura.
Invierte el tramo que copiaste para que la palabra se lea hacia delante.
Devuelve los primeros write caracteres.

def reverseWords(s):
    chars = list(s)

    def reverse(lo, hi):
        while lo < hi:
            chars[lo], chars[hi] = chars[hi], chars[lo]
            lo += 1
            hi -= 1

    n = len(chars)
    reverse(0, n - 1)  # words in the right order, each spelled backwards
    write = 0
    read = 0
    while read < n:
        if chars[read] == " ":
            read += 1
            continue
        if write > 0:
            chars[write] = " "  # one space before every word but the first
            write += 1
        start = write
        while read < n and chars[read] != " ":
            chars[write] = chars[read]
            write += 1
            read += 1
        reverse(start, write - 1)  # spell the word forwards again
    return "".join(chars[:write])

Errores comunes y casos límite

Dividir por un solo espacio y conservar cada fragmento. "a b" se divide en a, un fragmento vacío y b, y al unirlos se vuelven a poner dos espacios: "b a".
Confiar en que la división elimine los extremos. El método split(" ") de Java elimina los fragmentos vacíos del final, pero los conserva al principio, así que " a b" todavía deja uno.
Añadir un espacio después de cada palabra, incluida la última, de modo que la respuesta termine con un espacio. Pon el espacio antes de cada palabra, excepto la primera.
Hacer solo una inversión en la versión in situ. Invertir solo las palabras da como resultado yddoC snur ni 51 segaugnal.
En PHP y R, una entrada compuesta solo por dígitos, como 2026, puede recibirse como un número. Conviértela en una cadena antes de dividirla.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Invertir palabras en una cadena?

Ambos enfoques se ejecutan en tiempo O(n) para una cadena de longitud n, porque cada carácter se lee y se escribe una cantidad constante de veces. La división utiliza espacio adicional O(n) para la lista de palabras. Invertir la cadena completa y después cada palabra requiere espacio adicional O(1) en un arreglo de caracteres que puedes modificar.

¿Cómo manejas varios espacios entre palabras?

Considera una palabra como una secuencia de caracteres que no sean espacios y nunca copies espacios de la entrada. Una división sin separador en Python y Ruby, strings.Fields en Go y split_whitespace en Rust ya omiten cada secuencia de espacios y los espacios de ambos extremos; en otros casos, elimina las partes vacías. Después, escribe un espacio entre las palabras.

¿Puedes invertir las palabras sin una función split?

Sí. Recorre desde el extremo derecho: omite los espacios, marca dónde termina una palabra, desplázate a la izquierda hasta su inicio y añade la palabra con un espacio delante, a menos que sea la primera. Cada carácter se visita una vez, por lo que el tiempo sigue siendo O(n), y las palabras salen en orden inverso sin necesidad de invertir ninguna lista.

def reverseWords(s):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

s = "Coddy runs in 15 languages"

Salida Esperada

"languages 15 in runs Coddy"