Invertir el orden de las palabras
La misión
Problema
Una oración contiene palabras separadas por uno o más espacios, y además puede empezar o terminar con espacios. Devuelve un string (cadena) nuevo con las palabras en orden inverso, unidas por exactamente un espacio y sin espacios en ninguno de los extremos. Una palabra es cualquier serie de caracteres que no son espacios, y las letras dentro de una palabra conservan su orden.
Ejemplos
Input: s = " the sky is blue "
Output: "blue is sky the"
Por qué: los espacios sobrantes desaparecen y las palabras intercambian lugares
Input: s = "one"
Output: "one"
Por qué: una sola palabra no tiene con qué intercambiarse
Input: s = " "
Output: ""
Por qué: caso límite: solo espacios significa que no hay ninguna palabra
Pistas
0 / 3
Invertir todo el string también invierte las letras dentro de cada palabra, y eso no es lo que se pide. La unidad que se mueve es la palabra.
Si lees la oración desde el extremo derecho, las palabras llegan exactamente en el orden que necesita la respuesta.
Empieza en el último carácter y avanza hacia la izquierda. Salta los espacios y luego sigue avanzando hasta el siguiente espacio para encontrar dónde empieza la palabra actual, y guarda esa palabra. Repite hasta pasar el inicio y luego une las palabras guardadas con espacios simples.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Restricciones
- words are separated by one or more spaces
- leading and trailing spaces are possible
Solución
Recorrer desde la derecha encuentra primero la última palabra, así que reunir las palabras en el orden en que aparecen ya produce la oración invertida. Saltar las series de espacios antes de cada palabra descarta el espaciado sobrante, incluidos los espacios de ambos extremos. Las letras de cada palabra se extraen como un bloque con un slice, así que nunca cambian de orden. En el Python de todos los días, unir el resultado invertido de split da la misma respuesta en una línea. El tiempo es O(n) y el espacio es O(n) para la salida.
def reverse_words(s):
words, i = [], len(s) - 1
while i >= 0:
while i >= 0 and s[i] == " ":
i -= 1 # skip the gap before the next word
end = i
while i >= 0 and s[i] != " ":
i -= 1 # walk to the start of that word
if end > i:
words.append(s[i + 1:end + 1])
return " ".join(words)
print(reverse_words(" the sky is blue ")) # -> blue is sky the
print(reverse_words("one")) # -> one
print(reverse_words(" ")) # -> ""¿Lo que te frena es la idea y no el código? Invertir palabras lo explica.