Término de la secuencia look-and-say
La misión
Problema
La secuencia look-and-say (“mira y di”) empieza con “1”. Cada término siguiente se forma leyendo en voz alta el término anterior por series de dígitos iguales: “1” es un 1, lo que da “11”; “11” es dos 1, lo que da “21”; “21” es un 2 y luego un 1, lo que da “1211”. Dado n de al menos 1, devuelve el n-ésimo término como string (cadena).
Ejemplos
Input: n = 4
Output: "1211"
Input: n = 5
Output: "111221"
Por qué: "1211" se lee como un 1, un 2, dos 1
Input: n = 1
Output: "1"
Por qué: caso límite: el primer término ya viene dado, no hay nada que describir
Pistas
0 / 3
El n-ésimo término se define por completo a partir del término anterior. Esa es exactamente la forma de una definición recursiva.
El caso base es n igual a 1. Para cualquier n mayor, primero obtén el término n menos 1 y después descríbelo.
Para describir un string, recórrelo por series: desde el inicio de una serie, avanza mientras el dígito siga siendo el mismo, luego escribe la longitud de la serie seguida del dígito y continúa desde donde terminó la serie.
- Tiempo objetivo
- O(1.31ⁿ)
- Espacio objetivo
- O(1.31ⁿ)
Restricciones
- n ≥ 1
Solución
La definición ya es recursiva: el término 1 es “1” y el término n es la descripción del término n menos 1. Describir un string significa dividirlo en series de dígitos iguales y escribir cada serie como su longitud seguida del dígito, algo que se hace en una pasada con dos índices. La recursión tiene n niveles, lo cual no es problema para los n pequeños con que se usa esta secuencia, ya que los términos crecen aproximadamente un tercio en cada paso. El tiempo y el espacio son proporcionales a la longitud total de los términos producidos, dominada por la longitud del n-ésimo término.
def look_and_say(n):
if n == 1:
return "1" # base case
prev, out, i = look_and_say(n - 1), [], 0
while i < len(prev):
j = i
while j < len(prev) and prev[j] == prev[i]:
j += 1 # extend the run of prev[i]
out.append(str(j - i) + prev[i]) # count, then digit
i = j
return "".join(out)
print(look_and_say(4)) # -> 1211
print(look_and_say(5)) # -> 111221
print(look_and_say(1)) # -> 1
print(look_and_say(8)) # -> 1113213211¿Lo que te frena es la idea y no el código? Fundamentos de la recursión lo explica.