Decodificando Formas e Contando Caminhos
Resolva decode-ways — mapeamentos de dígitos para letras — como uma DP semelhante à de Fibonacci e conte caminhos em uma escada com passos de tamanhos variáveis.
Decodificando Formas e Contando Caminhos é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Problema das formas de decodificação
Formas de decodificação (LeetCode 91) mapeia uma cadeia de dígitos para letras: 'A'=1, 'B'=2, ..., 'Z'=26. Dada uma cadeia de dígitos codificada, conte o número de formas distintas de decodificá-la. Por exemplo, '12' pode ser decodificado como 'AB' (1+2) ou 'L' (12), resultando em 2 formas. '226' pode ser 'BZ' (2+26), 'VF' (22+6) ou 'BBF' (2+2+6), resultando em 3 formas. Zeros à esquerda tornam algumas decodificações inválidas.
# Encoding: A=1, B=2, ..., Z=26
# '12' → 'AB' or 'L' → 2 ways
# '226' → 'BZ' or 'VF' or 'BBF' → 3 ways
# '06' → invalid (no letter for '0')
# '10' → 'J' only → 1 way (only valid as 10, not 1+0)
s = '226'
print('Decodings for', s, ':', 3) # Expected: 3Formulação de DP para Maneiras de Decodificar
Defina dp[i] = número de maneiras de decodificar s[:i]. Casos base: dp[0] = 1 (cadeia vazia, uma maneira) e dp[1] = 1 se s[0] != '0'; caso contrário, 0. Transição: se s[i-1] != '0', some dp[i-1] (decodificação de um único dígito). Se 10 ≤ int(s[i-2:i]) ≤ 26, some dp[i-2] (decodificação de dois dígitos). Isso é essencialmente o padrão de Fibonacci com verificações de validade.
def num_decodings(s):
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # empty prefix
dp[1] = 0 if s[0] == '0' else 1
for i in range(2, n + 1):
# Single digit decode
if s[i-1] != '0':
dp[i] += dp[i-1]
# Two digit decode
two_digit = int(s[i-2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i-2]
return dp[n]
print(num_decodings('12')) # 2
print(num_decodings('226')) # 3
print(num_decodings('06')) # 0A Armadilha do Zero à Esquerda
A parte mais difícil de Maneiras de Decodificar é lidar com zeros. Um '0' isolado não pode ser decodificado (nenhuma letra corresponde a 0), portanto, se s[i-1] == '0', não some dp[i-1]. Um '0' como segundo dígito só é válido se o número de dois dígitos for 10 ou 20. '30' ou '40' (e números maiores) são inválidos, pois excedem 26. Verifique sempre 10 ≤ two_digit ≤ 26, e não apenas two_digit ≤ 26.
def num_decodings(s):
if not s or s[0] == '0': return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 # s[0] != '0' guaranteed by guard above
for i in range(2, n + 1):
one = int(s[i-1])
two = int(s[i-2:i])
if one != 0: dp[i] += dp[i-1] # valid single digit
if 10 <= two <= 26: dp[i] += dp[i-2] # valid two digits
return dp[n]
print(num_decodings('10')) # 1 (only 'J')
print(num_decodings('30')) # 0 (30 > 26, '0' alone invalid)
print(num_decodings('100')) # 0 (dp[2]=1 then '00' invalid, single '0' invalid)Maneiras de Decodificar com Espaço Otimizado
Assim como na sequência de Fibonacci, a recorrência de maneiras de decodificar considera apenas as duas posições anteriores, portanto, você pode reduzir o espaço de O(n) para O(1) usando duas variáveis. Use prev2 (duas etapas atrás) e prev1 (uma etapa atrás). Em cada etapa, calcule curr a partir das duas e, então, faça o deslocamento. Isso é idêntico à otimização de Fibonacci com duas variáveis.
def num_decodings_o1(s):
if not s or s[0] == '0': return 0
prev2 = 1 # dp[0]
prev1 = 1 # dp[1]
for i in range(2, len(s) + 1):
curr = 0
if s[i-1] != '0':
curr += prev1
two = int(s[i-2:i])
if 10 <= two <= 26:
curr += prev2
prev2, prev1 = prev1, curr
return prev1
print(num_decodings_o1('226')) # 3
print(num_decodings_o1('12')) # 2
print(num_decodings_o1('0')) # 0Contagem de Caminhos em uma Escada
Subir Escadas (LeetCode 70) pergunta: de quantas maneiras você pode subir n degraus se puder dar 1 ou 2 passos por vez? Esta é exatamente a sequência de Fibonacci: ways(n) = ways(n-1) + ways(n-2). ways(1)=1, ways(2)=2, ways(3)=3, ways(4)=5. Isso se generaliza quando você pode dar até k passos: ways(n) = sum(ways(n-1), ..., ways(n-k)).
def climb_stairs(n):
if n <= 2: return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1
for i in range(1, 8):
print(f'climb_stairs({i}) = {climb_stairs(i)}')
# 1, 2, 3, 5, 8, 13, 21 — Fibonacci!Subir Escadas com Passos Variáveis
Quando você pode dar qualquer número de passos de um conjunto fornecido (por exemplo, {1, 3, 5}), a recorrência se torna dp[i] = sum(dp[i-k] for k in steps if i-k >= 0). Use uma janela deslizante de tamanho max(steps) para obter eficiência de memória. Esta é a variante de contagem da mochila ilimitada — cada tamanho de passo pode ser usado qualquer número de vezes.
def count_ways(n, steps):
dp = [0] * (n + 1)
dp[0] = 1 # one way to stay at ground
for i in range(1, n + 1):
for step in steps:
if i >= step:
dp[i] += dp[i - step]
return dp[n]
# Steps of 1 or 2 (classic climbing stairs)
print(count_ways(5, [1, 2])) # 8
# Steps of 1, 3, or 5
print(count_ways(5, [1, 3, 5])) # 5
# Steps of 2 or 3
print(count_ways(6, [2, 3])) # 3 (2+2+2, 3+3, 2+4-invalid, 2+2+2, 3+3, 3+2+1-no...)Custo Mínimo para Subir Escadas
Custo Mínimo para Subir Escadas (LeetCode 746) associa um custo a cada degrau e solicita o custo mínimo para chegar ao topo. A partir do degrau i, você pode saltar para i+1 ou i+2. A recorrência é dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Você pode começar no degrau 0 ou no degrau 1. A resposta é min(dp[n-1], dp[n-2]).
def min_cost_climbing(cost):
n = len(cost)
if n == 1: return cost[0]
dp = [0] * n
dp[0] = cost[0]
dp[1] = cost[1]
for i in range(2, n):
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
return min(dp[-1], dp[-2]) # can start from step 0 or 1
print(min_cost_climbing([10, 15, 20])) # 15
print(min_cost_climbing([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])) # 6Maneiras de Decodificar II: Dígito Curinga
Maneiras de Decodificar II (LeetCode 639) introduz o caractere curinga '*' , que pode representar qualquer dígito de 1 a 9. Isso aumenta drasticamente o número de decodificações válidas. Um '*' isolado contribui com 9 maneiras (como qualquer dígito de 1 a 9). Dois '*' juntos podem formar 9×9 combinações de dois dígitos, mas apenas aquelas ≤ 26 são válidas (11-19 = 9 maneiras, 21-26 = 6 maneiras → 15 maneiras para '**'). É necessária uma análise cuidadosa dos casos.
def num_decodings_ii(s):
MOD = 10**9 + 7
prev2, prev1 = 1, 9 if s[0] == '*' else (0 if s[0] == '0' else 1)
for i in range(1, len(s)):
curr = 0
c, p = s[i], s[i-1]
# Single digit
if c == '*': curr += 9 * prev1
elif c != '0': curr += prev1
# Two digits
if p == '*' and c == '*': curr += 15 * prev2 # 11-19(9) + 21-26(6)
elif p == '*': curr += (2 if c <= '6' else 1) * prev2
elif c == '*': curr += (9 if p == '1' else (6 if p == '2' else 0)) * prev2
else:
two = int(p + c)
if 10 <= two <= 26: curr += prev2
prev2, prev1 = prev1, curr % MOD
return prev1 % MOD
print(num_decodings_ii('*')) # 9
print(num_decodings_ii('1*')) # 18Conexão com Fibonacci
Tanto Maneiras de Decodificar quanto Subir Escadas são problemas da família de Fibonacci disfarçados. Qualquer DP em que dp[i] dependa apenas de dp[i-1] e dp[i-2] tem formato de Fibonacci e pode ser resolvido com espaço O(1). As verificações de validade (dígitos zero, tamanhos dos passos) modificam quais transições estão ativas, mas não a estrutura fundamental de olhar duas posições para trás. Reconhecer essa família imediatamente é um padrão valioso para ganhar velocidade em entrevistas.
# Fibonacci family: dp[i] = f(dp[i-1], dp[i-2])
# Fibonacci itself: dp[i] = dp[i-1] + dp[i-2]
# Climbing stairs: dp[i] = dp[i-1] + dp[i-2]
# Decode ways: dp[i] = (dp[i-1] if one_valid) + (dp[i-2] if two_valid)
# Min cost stairs: dp[i] = cost[i] + min(dp[i-1], dp[i-2])
# House robber: dp[i] = max(dp[i-1], nums[i] + dp[i-2])
# All solved with 2 rolling variables:
prev2, prev1 = 0, 1
for _ in range(10):
prev2, prev1 = prev1, prev1 + prev2
print('Fibonacci F(10):', prev1) # 89Contagem de Caminhos em uma Grade
Um problema de contagem relacionado: dada uma grade m×n, quantos caminhos únicos vão do canto superior esquerdo ao canto inferior direito se você só puder mover-se para a direita ou para baixo? A resposta é o coeficiente binomial C(m+n-2, m-1). A solução com DP preenche uma tabela 2D em que dp[i][j] = dp[i-1][j] + dp[i][j-1]. Esta é uma versão 2D da escada de Fibonacci — cada célula é a soma da célula acima e da célula à esquerda.
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
# Or use math for O(1) solution
import math
def unique_paths_math(m, n):
return math.comb(m + n - 2, m - 1)
print(unique_paths(3, 7)) # 28
print(unique_paths_math(3, 7)) # 28
print(unique_paths(3, 3)) # 6Resumo das Armadilhas em Entrevistas
Armadilhas comuns em Maneiras de Decodificar: (1) esquecer que '0' sozinho é inválido — verifique sempre s[i-1] != '0' antes de adicionar dp[i-1]. (2) Usar two_digit <= 26 sem verificar two_digit >= 10 — '07' não deve ser decodificado como 'G'. (3) Retornar dp[n-1] em vez de dp[n] — a tabela é indexada a partir de 1, portanto dp[n] corresponde à cadeia completa. Sempre confira novamente os índices do vetor quando sua tabela de DP tiver um elemento a mais que a entrada.
# Common bug: checking two_digit <= 26 without >= 10
def buggy_decode(s):
dp = [0] * (len(s) + 1)
dp[0] = dp[1] = 1
for i in range(2, len(s) + 1):
if s[i-1] != '0': dp[i] += dp[i-1]
two = int(s[i-2:i])
# BUG: '07' gives two=7, and 7 <= 26 would add dp[i-2]
# Fix: require two >= 10
if 10 <= two <= 26: dp[i] += dp[i-2] # CORRECT
return dp[len(s)]
print(buggy_decode('06')) # 0 (correct, '0' alone invalid)
print(buggy_decode('07')) # 0 (correct, '07' not valid, '0' alone invalid)
print(buggy_decode('27')) # 1 (only 'BG', 27>26 so no two-digit)Verificação Rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Resumo da Lição
Nesta lição, você aprendeu: Maneiras de Decodificar segue uma recorrência semelhante à de Fibonacci, com condições de validade para decodificações de um dígito (diferente de zero) e de dois dígitos (10-26), Subir Escadas e Escada de Custo Mínimo são variantes puras de Fibonacci resolvíveis com espaço O(1) e reconhecer a família de Fibonacci que olha duas posições para trás economiza um tempo significativo durante entrevistas. Em seguida, exploraremos DP bidimensional com Caminhos Únicos e Soma Mínima de Caminho em grades.
Perguntas Frequentes
A aula “Decodificando Formas e Contando Caminhos” é grátis?
Sim — o texto completo de “Decodificando Formas e Contando Caminhos” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Decodificando Formas e Contando Caminhos”?
Resolva decode-ways — mapeamentos de dígitos para letras — como uma DP semelhante à de Fibonacci e conte caminhos em uma escada com passos de tamanhos variáveis. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Decodificando Formas e Contando Caminhos”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- House Robber: Recorrência Escolher ou Ignorar
- Subarray Máximo e Subarray de Produto Máximo
- Quebra de Palavras e Segmentação de Strings
- Decodificando Formas e Contando Caminhos