Strings binarios sin unos adyacentes
La misión
Problema
Dada una longitud n, devuelve todos los strings (cadenas) binarios de esa longitud en los que no haya dos 1 seguidos. Devuelve los strings en orden creciente.
Ejemplos
Input: n = 3
Output: ["000", "001", "010", "100", "101"]
Por qué: 011, 110 y 111 ponen cada uno dos 1 juntos
Input: n = 1
Output: ["0", "1"]
Input: n = 0
Output: [""]
Por qué: caso límite: el string vacío es el único string de longitud cero
Pistas
0 / 3
Generar los 2 elevado a n strings y filtrarlos desperdicia trabajo en strings que ya rompieron la regla en su segundo carácter. ¿Puedes detener un string inválido en cuanto falla?
Construye el string carácter por carácter. En cada posición las opciones son 0 y 1, y el 1 solo se permite cuando el carácter anterior no es 1.
Escribe una función auxiliar recursiva que agregue 0, llame recursivamente y lo quite; y luego, solo si el string está vacío o termina en 0, que agregue 1, llame recursivamente y lo quite. Probar 0 antes que 1 produce los strings en orden creciente.
- Tiempo objetivo
- O(n · 1.62ⁿ)
- Espacio objetivo
- O(n · 1.62ⁿ)
Solución
Cada posición es un nivel del árbol de decisión con dos ramas, 0 y 1, y la regla poda la rama del 1 siempre que el carácter anterior ya sea 1. Una rama podada nunca se explora, así que cada hoja a la que llega la búsqueda es un string válido y no hay que filtrar nada después. Probar 0 antes que 1 en cada nivel visita las hojas en orden creciente. La cantidad de strings válidos crece como los números de Fibonacci, y unir cada uno cuesta O(n), así que el tiempo es O(n · F(n + 2)) y la recursión usa O(n) de espacio extra además de la salida.
def no_adjacent_ones(n):
result, path = [], []
def build():
if len(path) == n:
result.append("".join(path))
return
path.append("0")
build()
path.pop()
if not path or path[-1] == "0": # prune: a 1 may not follow a 1
path.append("1")
build()
path.pop()
build()
return result
print(no_adjacent_ones(3)) # -> ['000', '001', '010', '100', '101']
print(no_adjacent_ones(1)) # -> ['0', '1']
print(no_adjacent_ones(0)) # -> ['']¿Lo que te frena es la idea y no el código? El árbol de decisión lo explica.