Strings binárias sem 1s adjacentes
A missão
Problema
Dado um tamanho n, retorne todas as strings binárias desse tamanho em que nenhum par de 1s fica lado a lado. Retorne as strings em ordem crescente.
Exemplos
Input: n = 3
Output: ["000", "001", "010", "100", "101"]
Por quê: 011, 110 e 111 colocam dois 1s lado a lado
Input: n = 1
Output: ["0", "1"]
Input: n = 0
Output: [""]
Por quê: edge case: a string vazia é a única string de tamanho zero
Dicas
0 / 3
Gerar todas as 2 elevado a n strings e filtrá-las desperdiça trabalho com strings que quebraram a regra já no segundo caractere. Dá para interromper uma string ruim assim que ela dá errado?
Monte a string um caractere por vez. Em cada posição, as escolhas são 0 e 1, e o 1 só é permitido quando o caractere anterior não é 1.
Escreva uma função auxiliar recursiva que adiciona 0, chama recursivamente e o remove; depois, adiciona 1 só quando a string está vazia ou termina em 0, chama recursivamente e o remove. Tentar 0 antes de 1 produz as strings em ordem crescente.
- Tempo-alvo
- O(n · 1.62ⁿ)
- Espaço-alvo
- O(n · 1.62ⁿ)
Solução
Cada posição é um nível da árvore de decisão com dois ramos, 0 e 1, e a regra poda o ramo do 1 sempre que o caractere anterior já é 1. Um ramo podado nunca é explorado, então toda folha que a busca alcança é uma string válida e nada é filtrado depois. Tentar 0 antes de 1 em cada nível visita as folhas em ordem crescente. O número de strings válidas cresce como os números de Fibonacci, e cada uma custa O(n) para ser montada, então o tempo é O(n · F(n + 2)) e a recursão usa O(n) de espaço extra além da saída.
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)) # -> ['']Travou na ideia, e não no código? A árvore de decisão explica isso.