Generate Parentheses

Q: Qual é a complexidade de tempo de Generate Parentheses?

O retrocesso produz C(n) = (2n)! / ((n+1)! n!) strings, o número de Catalan, que cresce como 4^n / (n^1.5 √π) . Cada uma leva O(n) para ser construída e copiada, então o tempo é O(4^n / √n) . O espaço extra é O(n) para a string atual e a pilha de chamadas, além da saída.

Q: Quantas strings de parênteses válidas existem para n pares?

Os números de Catalan: 1, 2, 5, 14, 42, 132, 429 e 1.430 para n de 1 a 8. Toda string bem-formada se divide em ( A ) B, em que esse ) corresponde ao primeiro ( , e A e B compartilham n - 1 pares. Somando os tamanhos de A, obtém-se a recorrência de Catalan.

Q: É possível resolver Generate Parentheses sem recursão?

Sim. Mantenha uma pilha de estados parciais, cada um sendo uma string com seus dois contadores, e expanda cada estado pelas mesmas duas regras. Empilhe a extensão ) antes da extensão ( , para que a extensão ( seja desempilhada primeiro e a saída permaneça ordenada.

MédioBacktracking Recursão

+10

Uma sequência de parênteses está bem formada quando, ao lê-la da esquerda para a direita, a contagem de ) nunca ultrapassa a contagem de (, e as duas contagens são iguais no final. Portanto, (())() está bem formada, enquanto ())( não está: seu terceiro caractere fecha um par que nunca foi aberto.

Dado um inteiro n, retorne todas as sequências bem formadas com n parênteses de abertura e n parênteses de fechamento, ordenadas em ordem lexicográfica, na qual ( vem antes de ).

Função

generateParenthesis(n: integer) → string-array

ninteger: o número de pares de parênteses
Retornastring-array: toda string bem formada de n pares, em ordem lexicográfica

Restrições

1 ≤ n ≤ 8
Para n = 8, a resposta é 1.430 strings.

Exemplos

Entrada: n = 3
Saída: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Explicação: Três pares formam cinco strings bem formadas. ((())) abre os três primeiro, então vem primeiro na ordenação; ()()() fecha cada par de uma só vez e fica por último.

Entrada: n = 1
Saída: ["()"]
Explicação: Um par tem uma string bem formada. O único outro arranjo, )(, fecha antes que algo esteja aberto.

Para ir além

Você consegue contar as strings bem formadas para n pares sem gerá-las?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Poucas strings de comprimento 2n são bem formadas: 1.430 de 65.536 para n = 8. Construa cada string da esquerda para a direita e adicione um caractere somente quando ainda for possível completar o prefixo. Dois contadores determinam isso, e tentar ( antes de ) faz com que as strings saiam ordenadas.

Construa cada string e depois verifique-a

Intuição

Preencha as posições 2n com todas as combinações de ( e ), 4^n strings, e mantenha as que são bem formadas. Para verificar uma string, percorra-a mantendo um saldo: mais 1 para (, menos 1 para ). Ela é bem formada quando o saldo nunca fica abaixo de 0 e termina em 0. Colocar ( antes de ) em cada posição lista as strings em ordem crescente.

Verificar cada string custa O(n). Para n = 8, são 65.536 strings para 1.430 respostas, então cerca de 98% do trabalho é descartado, e a quantidade quadruplica a cada par extra.

Algoritmo

Mantenha um buffer de 2n caracteres e uma lista para as respostas.
fill(pos): se pos for igual a 2n, salve o buffer se ele estiver bem formado.
Caso contrário, coloque ( em pos e chame fill(pos + 1); depois, coloque )</code nessa posição e chame a função novamente.</li><li>Para verificar, some 1 para cada <code>( e subtraia 1 para cada ). Rejeite quando o saldo ficar abaixo de 0 ou não terminar em 0.
Chame fill(0) e retorne as strings salvas.

def generateParenthesis(n):
    result = []
    path = []

    def is_balanced(text):
        balance = 0
        for ch in text:
            balance += 1 if ch == "(" else -1
            if balance < 0:
                return False  # a ")" with nothing open to close
        return balance == 0

    def fill():
        if len(path) == 2 * n:
            text = "".join(path)
            if is_balanced(text):
                result.append(text)
            return
        for ch in "()":  # "(" first keeps the output sorted
            path.append(ch)
            fill()
            path.pop()

    fill()
    return result

Retroceda nas contagens de abertura e fechamento

Intuição

Mova a verificação para dentro da construção. Um prefixo pode crescer até formar uma string bem formada exatamente quando usa no máximo n de ( e nunca tem mais ) do que (. Portanto, ( é permitido enquanto opened < n, e ) enquanto closed < opened. No comprimento 2n, ambas as contagens são n, e a string está bem formada, sem nada que reste verificar.

Nenhuma resposta é perdida, porque todo prefixo de uma string bem formada obedece às duas regras. Nenhum ramo é desperdiçado: para n = 2, o ramo (( só pode fechar duas vezes, gerando (()), e o ramo () só pode abrir e fechar, gerando ()(). Cada string corresponde a um caminho pela árvore, então aparece uma única vez, e o ramo ( vem primeiro, portanto a saída está ordenada.

Toda folha é uma resposta, então o trabalho é proporcional à saída: O(4^n / √n).

Algoritmo

Mantenha a string que está sendo construída e dois contadores, opened e closed, ambos com valor 0.
Se a string tiver comprimento 2n, salve uma cópia e retorne.
Se opened < n, adicione (, faça a chamada recursiva com opened + 1 e remova-o.
Se closed < opened, adicione ), faça a chamada recursiva com closed + 1 e remova-o.
Comece com a string vazia e retorne as strings salvas.

def generateParenthesis(n):
    result = []
    path = []

    def backtrack(opened, closed):
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        # "(" sorts before ")", so trying it first keeps the output sorted
        if opened < n:
            path.append("(")
            backtrack(opened + 1, closed)
            path.pop()
        if closed < opened:  # only close a pair that is open
            path.append(")")
            backtrack(opened, closed + 1)
            path.pop()

    backtrack(0, 0)
    return result

Armadilhas e casos extremos

Permitir ) enquanto closed < n em vez de closed < opened. Isso produz ())(, que fecha um par que nunca foi aberto.
Verificar apenas se as contagens coincidem no final. Isso aceita )(; o saldo deve permanecer em 0 ou acima em cada etapa.
Tentar ) antes de (. As strings corretas são geradas na ordem inversa.
Salvar o buffer compartilhado em vez de uma cópia, quando listas ou construtores de strings são mutáveis. Então, todas as respostas salvas exibem o mesmo buffer, que o retrocesso esvazia novamente.
Dimensionar um array de resultados fixo com base em uma estimativa baixa. n = 8 tem 1.430 respostas.

Perguntas frequentes3

Qual é a complexidade de tempo de Generate Parentheses?

O retrocesso produz C(n) = (2n)! / ((n+1)! n!) strings, o número de Catalan, que cresce como 4^n / (n^1.5 √π). Cada uma leva O(n) para ser construída e copiada, então o tempo é O(4^n / √n). O espaço extra é O(n) para a string atual e a pilha de chamadas, além da saída.

Quantas strings de parênteses válidas existem para n pares?

Os números de Catalan: 1, 2, 5, 14, 42, 132, 429 e 1.430 para n de 1 a 8. Toda string bem-formada se divide em ( A ) B, em que esse ) corresponde ao primeiro (, e A e B compartilham n - 1 pares. Somando os tamanhos de A, obtém-se a recorrência de Catalan.

É possível resolver Generate Parentheses sem recursão?

Sim. Mantenha uma pilha de estados parciais, cada um sendo uma string com seus dois contadores, e expanda cada estado pelas mesmas duas regras. Empilhe a extensão ) antes da extensão (, para que a extensão ( seja desempilhada primeiro e a saída permaneça ordenada.

def generateParenthesis(n):
    # Escreva o código aqui

Teste #1

Teste #2

Argumento

n = 3

Saída Esperada

["((()))", "(()())", "(())()", "()(())", "()()()"]