Decode Ways

Q: Como lidar com zeros em Decode Ways?

Um 0 nunca é uma letra sozinho, então ele deve formar par com o dígito anterior, como em 10 ou 20 . Ele adiciona a contagem de dois dígitos atrás somente após um 1 ou um 2, e nada nos outros casos. Um 0 inicial, dois zeros seguidos ou um 0 após 3 a 9 resulta em 0.

MédioProgramação dinâmica

+10

Uma mensagem composta por letras maiúsculas foi codificada com A = 1, B = 2 e assim por diante até Z = 26, e os códigos foram escritos sem separadores. Dada a sequência de dígitos s, retorne quantas mensagens poderiam tê-la produzido.

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

Função

numDecodings(s: string) → integer

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

Restrições

1 ≤ s.length ≤ 100
s contém apenas os dígitos 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ê construir 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 formar par com o 2 que vem antes dele, como 20, o que força 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 string.

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), 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 corresponde a uma letra sozinho ou se junta ao vizinho, então as interpretações crescem como os números de Fibonacci: 45 algarismos 1 têm 1836311903 interpretações. Listá-las é inviável, mas as maneiras de concluir uma interpretação dependem apenas da posição alcançada, então cada posição precisa ser contada uma vez. Um 0 só pode encerrar 10 ou 20.

Experimente as duas leituras com recursão

Correta, mas não termina nos maiores testes

Intuição

No índice i, um 0 não inicia nenhuma letra, então o caminho não gera nenhuma interpretação. Caso contrário, leia um dígito e conte o restante a partir de i+1; se os dois dígitos formarem um número de 10 a 26, leia também ambos e conte a partir de i+2. As duas escolhas geram letras iniciais diferentes, então suas contagens são somadas sem sobreposição, e chegar ao fim completa uma interpretação.

Nada é armazenado, então as chamadas seguem a regra de Fibonacci: 45 algarismos 1 exigem cerca de 5 × 10^9 chamadas. Uma resposta igual a 0 não é mais rápida: 44 algarismos 1, 55 algarismos 3 e um 0 final exigem cerca de 10^11 chamadas, já que cada interpretação dos algarismos 1 só chega a um impasse no último dígito.

Algoritmo

waysFrom(i) conta as leituras dos dígitos a partir do índice i.
No final da string, retorne 1. Em um 0, retorne 0.
Caso contrário, retorne waysFrom(i+1), mais waysFrom(i+2) quando os dígitos i e i+1 formarem um número de no máximo 26.
A resposta é 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 muitas vezes. 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 é a mesma em todas as vezes, porque depende apenas dos dígitos a partir do índice 3. Armazene cada contagem na primeira vez que a calcular e marque as posições ainda não calculadas com -1, já que 0 é uma contagem válida.

Há n posições, cada uma calculada uma única vez com trabalho constante: tempo O(n). A memoização e a pilha de chamadas ocupam espaço O(n), com no máximo 100 chamadas de profundidade.

Algoritmo

Preencha memo com -1, uma posição por índice.
Em waysFrom(i), retorne 1 no final da string e memo[i] quando ele não for -1.
Caso contrário, conte como na recursão simples, salve a contagem em memo[i], inclusive zero, e retorne-a.

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

Conte os prefixos em vez disso. Seja ways(i) o número de leituras dos primeiros i dígitos. A última letra é o dígito i-1 sozinho, que precisa estar entre 1 e 9 e deixa ways(i-1) leituras, ou os dígitos i-2 e i-1 juntos, que devem formar um número entre 10 e 26 e deixar ways(i-2). Some as partes cuja condição é satisfeita. O prefixo vazio tem uma leitura, então ways(0) = 1.

Em "1203", as contagens são 1, 2 e então voltam a 1 no 0, porque somente 20 funciona e deixa a contagem anterior ao 2. O 3 fica sozinho, então a contagem permanece 1. Cada contagem consulta duas posições anteriores, então duas variáveis substituem a tabela: tempo O(n), espaço O(1).

Algoritmo

Defina twoBack = 0 e oneBack = 1, a contagem para o prefixo vazio.
Para cada índice i, defina current como oneBack se o dígito i não for 0; caso contrário, como 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, some twoBack.
Desloque: twoBack = oneBack e, em seguida, oneBack = current.
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

Considerar 0 como uma letra ou 06 como 6. "30", "100" e "06" todos têm 0 interpretações.
Testar uma sequência de dois dígitos apenas com ≤ 26. 05 é 5 como número, mas não como código, então verifique se o primeiro dígito não é 0.
Marcar posições desconhecidas da memoização com 0. Posições com 0 interpretações nunca são consideradas armazenadas: com 44 uns, 55 três e um 0 final, você volta a 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.
Transformar s em um único número. Cem dígitos não cabem em nenhum tipo inteiro, e os zeros à esquerda que mudam a resposta se perdem.

Perguntas frequentes3

Qual é a complexidade de tempo de Decode Ways?

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

Como Decode Ways se relaciona com Climbing Stairs?

Ambos contam as maneiras de cobrir uma linha com passos de 1 e 2. Em Climbing Stairs, todos os passos são permitidos, então as contagens são números de Fibonacci. Em Decode Ways, um passo de um dígito precisa estar entre 1 e 9, e um passo de dois dígitos precisa estar entre 10 e 26, então cada termo só é adicionado quando sua condição é satisfeita.

Como lidar com zeros em Decode Ways?

Um 0 nunca é uma letra sozinho, então ele deve formar par com o dígito anterior, como em 10 ou 20. Ele adiciona a contagem de dois dígitos atrás somente após um 1 ou um 2, e nada nos outros casos. Um 0 inicial, dois zeros seguidos ou um 0 após 3 a 9 resulta em 0.

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

Teste #1

Teste #2

Teste #3

Argumento

s = "2611"

Saída Esperada

Decode Ways

Função

Restrições

Exemplos

Dicas

Solução

Experimente as duas leituras com recursão

Recursão com memoização

De baixo para cima com dois contadores

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos