Decode Ways

Q: Como lidar com zeros em Decode Ways?

Um 0 nunca pode ser uma letra por si só, então precisa se juntar ao dígito que vem antes dele, e apenas 10 e 20 são códigos. No loop de baixo para cima, isso significa que um 0 não acrescenta nada no caso de um dígito e só acrescenta a contagem de dois dígitos atrás depois de um 1 ou um 2. Um 0 no início, dois zeros seguidos ou um 0 depois de um dígito de 3 a 9 faz a resposta ser 0.

MédioProgramação dinâmica

+10

Uma mensagem escrita em letras maiúsculas foi transformada em dígitos usando o código A = 1, B = 2 e assim por diante até Z = 26, e os códigos foram escritos um após o outro, sem separadores. Você recebe a sequência de dígitos s. Retorne quantas mensagens diferentes poderiam tê-la produzido.

Cada letra é lida a partir de um dígito ou de dois dígitos adjacentes, e um código nunca começa com 0: 06 não é 6, e um 0 sozinho não é uma letra. Se nenhuma leitura funcionar, retorne 0.

Função

numDecodings(s: string) → integer

sstring: a sequência de dígitos a ser decodificada
Retornainteger: o número de mensagens de letras que são codificadas em s

Restrições

1 ≤ s.length ≤ 100
s contém apenas os dígitos de 0 a 9, e pode começar com 0.
Todo prefixo e todo sufixo de s têm menos de 2³¹ leituras, então a resposta e todas as contagens que você calcular ao longo do caminho cabem em um inteiro de 32 bits com sinal.

Exemplos

Entrada: s = "2611"
Saída: 4
Explicação: As quatro leituras são 2 6 1 1 (BFAA), 26 1 1 (ZAA), 2 6 11 (BFK) e 26 11 (ZK). Os dígitos do meio nunca formam um par, porque 61 é maior que 26.

Entrada: s = "1203"
Saída: 1
Explicação: O 0 precisa se juntar ao 2 que vem antes dele, formando 20, o que força a leitura 1 20 3 (ATC). Ler 12 primeiro deixaria o 0 sozinho, e 03 começa com 0.

Entrada: s = "06"
Saída: 0
Explicação: A primeira letra teria que começar com 0. Um 0 sozinho não é uma letra, e 06 não é um código, então nenhuma mensagem gera essa sequência.

+25 testes ocultos ao enviar

Para ir além

E se s também puder conter *, que representa qualquer dígito de 1 a 9? Você consegue contar as leituras em tempo O(n), retornando a contagem módulo 10^9+7?

Dicas

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

0 de 3 abertas

Solução

Cada dígito é uma letra por si só ou se junta ao vizinho para formar uma letra de dois dígitos, então o número de interpretações cresce como os números de Fibonacci: 45 algarismos 1 já têm 1836311903 interpretações. Listar as interpretações é impossível. O que resolve o problema é que o número de maneiras de concluir uma interpretação depende apenas da posição alcançada, então cada posição precisa ser contada uma vez. É preciso ter cuidado com os zeros: um 0 só pode ser o segundo dígito de 10 ou 20.

Experimente ambas as leituras com recursão

Correta, mas não termina nos maiores testes

Intuição

Posicione-se no índice i e observe o próximo dígito. Se for 0, nenhuma letra começa aqui e este caminho não gera nenhuma leitura. Caso contrário, você pode ler esse dígito como uma letra e contar as leituras do restante a partir de i+1. Se, junto com o dígito seguinte, ele formar um número de 10 a 26, você também pode ler os dois como uma letra e contar a partir de i+2. As duas opções geram letras iniciais diferentes, então suas contagens se somam sem sobreposição. Quando i chega ao fim da string, você concluiu uma leitura completa, então retorna 1.

Em "2611": a primeira letra é 2 ou 26. Depois de 2, a próxima letra precisa ser 6, porque 61 é grande demais. Os dois ramos terminam então com 1 1 ou 11, então o total é 2 × 2 = 4.

A resposta está correta, mas nada é armazenado. Em uma string de uns, cada chamada se ramifica em duas e as chamadas seguem a regra de Fibonacci, então 45 uns exigem cerca de 5 × 10^9 chamadas. O trabalho também não diminui junto com a resposta: em 44 uns seguidos por 55 três e um 0 final, a resposta é 0, mas a recursão percorre todas as leituras dos uns ao longo de todos os três antes de cada caminho morrer no último dígito, cerca de 10^11 chamadas.

Algoritmo

Escreva uma função auxiliar waysFrom(i) que conte as leituras dos dígitos do índice i até o final.
Se i for igual ao comprimento de s, retorne 1.
Se o dígito no índice i for 0, retorne 0.
Comece com waysFrom(i+1), as leituras cuja próxima letra usa um dígito.
Se os dígitos i e i+1 formarem um número de no máximo 26, some waysFrom(i+2). Retorne waysFrom(0).

def numDecodings(s):
    n = len(s)

    def ways_from(i):
        # The number of ways to decode s[i:].
        if i == n:
            return 1  # nothing left: one finished reading
        if s[i] == "0":
            return 0  # no letter code starts with 0
        ways = ways_from(i + 1)  # read one digit
        if i + 1 < n and int(s[i:i + 2]) <= 26:
            ways += ways_from(i + 2)  # read two digits, 10 to 26
        return ways

    return ways_from(0)

Recursão com memoização

Intuição

A recursão faz a mesma pergunta repetidamente. Em "11111", a contagem a partir do índice 3 é necessária depois de 1 1 1, depois de 11 1 e depois de 1 11, e o resultado é o mesmo todas as vezes, porque depende apenas dos dígitos a partir do índice 3. Armazene cada contagem em um array memo na primeira vez que calculá-la e, depois, leia-a de lá.

Marque as posições que ainda não foram calculadas com -1, não com 0. Zero é uma resposta válida aqui: em uma string que termina em 30, todas as posições têm 0 leituras. Com 0 como marcação, essas posições parecem desconhecidas em todas as visitas, e a recursão continua tão lenta quanto antes.

Há n posições, e cada uma é calculada uma vez com trabalho constante, então o tempo é O(n). O memo e a pilha de chamadas ocupam, cada um, O(n) de espaço. As chamadas se aninham no máximo 100 níveis aqui, o que qualquer linguagem consegue lidar.

Algoritmo

Crie um array memo com uma posição para cada índice, todas definidas como -1.
Em waysFrom(i), retorne 1 no final da string e memo[i] quando seu valor não for -1.
Caso contrário, conte como na recursão simples: 0 para um 0; caso contrário, waysFrom(i+1) mais waysFrom(i+2) quando os dois dígitos formarem um número de 10 a 26.
Salve a contagem em memo[i], inclusive se for zero, e retorne-a.
Retorne waysFrom(0).

def numDecodings(s):
    n = len(s)
    memo = [-1] * n  # memo[i]: ways to decode s[i:], -1 until worked out

    def ways_from(i):
        if i == n:
            return 1
        if memo[i] != -1:
            return memo[i]
        ways = 0
        if s[i] != "0":
            ways = ways_from(i + 1)  # read one digit
            if i + 1 < n and int(s[i:i + 2]) <= 26:
                ways += ways_from(i + 2)  # read two digits, 10 to 26
        memo[i] = ways
        return ways

    return ways_from(0)

De baixo para cima com dois contadores

Intuição

Inverta a recursão e conte os prefixos. Seja ways(i) o número de leituras dos primeiros i dígitos. A última letra de uma leitura desse tipo é o dígito no índice i-1 sozinho, que precisa ser de 1 a 9 e deixa ways(i-1) leituras para o restante, ou os dois dígitos nos índices i-2 e i-1, que precisam formar um número de 10 a 26 e deixam ways(i-2). Portanto, ways(i) é a soma das partes cuja condição é satisfeita. O prefixo vazio tem uma leitura, a mensagem vazia, então ways(0) = 1.

Percorra "1203". Depois de 1, a contagem é 1. Depois de 12, ela é 2: 1 2 e 12. O 0 não pode aparecer sozinho, e apenas 20 funciona, então a contagem volta à contagem de antes do 2, que é 1. O 3 aparece sozinho, e 03 não é um código, então a contagem permanece 1.

Cada contagem consulta apenas as duas anteriores, então duas variáveis, twoBack e oneBack, substituem a tabela. Isso exige uma única passagem com trabalho constante por dígito: tempo O(n), espaço O(1) e nenhuma recursão.

Algoritmo

Defina twoBack = 0 e oneBack = 1, a contagem para o prefixo vazio.
Para cada índice i, comece com current igual a 0 e adicione oneBack se o dígito i não for 0.
Se i ≥ 1, o dígito i-1 não for 0 e os dígitos i-1 e i formarem um número de no máximo 26, adicione twoBack.
Desloque os valores: twoBack = oneBack e, em seguida, oneBack = current.
Após o último dígito, retorne oneBack.

def numDecodings(s):
    # ways(i) counts the readings of the first i digits; ways(0) = 1.
    two_back, one_back = 0, 1  # ways(i-1) and ways(i) before digit i is read
    for i in range(len(s)):
        current = 0
        if s[i] != "0":
            current = one_back  # digit i is a letter on its own
        if i >= 1 and s[i - 1] != "0" and int(s[i - 1:i + 1]) <= 26:
            current += two_back  # digits i-1 and i form one letter, 10 to 26
        two_back, one_back = one_back, current
    return one_back

Armadilhas e casos extremos

Quase todas as respostas erradas para este problema são causadas pelos zeros ou por uma memoização que esquece resultados.

Tratar 0 como uma letra ou 06 como 6. Um zero só pode completar 10 ou 20, então "30", "100" e "06" têm todos 0 decodificações.
Testar um trecho de dois dígitos usando apenas ≤ 26. 05 é 5 como número, mas não é um código. Verifique se o primeiro dos dois dígitos não é 0.
Usar 0 como marca para uma posição da memoização que ainda não foi calculada. Muitas posições realmente têm 0 decodificações, então essas posições nunca são consideradas armazenadas e são recalculadas a cada visita. Para 44 algarismos 1 seguidos de algarismos 3 e um 0 final, todas as posições são 0 e você volta a ter cerca de 10^11 chamadas.
Ler o dígito antes do índice 0. Proteja a verificação de dois dígitos com i ≥ 1: em Python, s[-1] lê silenciosamente o último dígito, e outras linguagens leem fora da string.
Transformar s em um único número. Cem dígitos não cabem em nenhum tipo inteiro, e a conversão remove zeros à esquerda, o que altera a resposta. Trabalhe dígito por dígito.
Em Lua e R, as posições começam em 1, então o fim da string é a posição n+1 e a primeira verificação de dois dígitos é na posição 2.

Perguntas frequentes4

Qual é a complexidade de tempo de Decode Ways?

A solução de baixo para cima lê cada dígito uma vez, com trabalho constante, então executa em O(n) de tempo e usa O(1) de espaço extra. A recursão com memoização também tem tempo O(n), mas usa O(n) de espaço para a memoização e a pilha de chamadas. A recursão simples é exponencial: em uma string de uns, o número de chamadas cresce como 1.618^n.

Qual é a relação entre Decode Ways e Climbing Stairs?

Ambos contam as maneiras de cobrir uma linha com passos de tamanho 1 e 2. Em Climbing Stairs, todos os passos são permitidos, então a contagem é um número de Fibonacci. Em Decode Ways, um passo de um dígito precisa de um dígito de 1 a 9, e um passo de dois dígitos precisa de um número de 10 a 26, então cada termo da soma é adicionado somente quando sua condição é satisfeita. Uma string de uns permite todos os passos, e suas contagens são exatamente os números de Fibonacci.

Como lidar com zeros em Decode Ways?

Um 0 nunca pode ser uma letra por si só, então precisa se juntar ao dígito que vem antes dele, e apenas 10 e 20 são códigos. No loop de baixo para cima, isso significa que um 0 não acrescenta nada no caso de um dígito e só acrescenta a contagem de dois dígitos atrás depois de um 1 ou um 2. Um 0 no início, dois zeros seguidos ou um 0 depois de um dígito de 3 a 9 faz a resposta ser 0.

É possível resolver Decode Ways com espaço O(1)?

Sim. A contagem para um prefixo depende apenas das contagens dos dois prefixos com um e dois dígitos a menos, então duas variáveis substituem a tabela inteira. A cada etapa, calcula-se a nova contagem a partir delas e elas avançam uma posição.

Python

def numDecodings(s):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

s = "2611"

Esperado

Decode Ways

Função

Restrições

Exemplos

Dicas

Solução

Experimente ambas as leituras com recursão

Recursão com memoização

De baixo para cima com dois contadores

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos