Valid Sudoku (LeetCode 36) te dá um tabuleiro 9 por 9 parcialmente preenchido e pergunta se as células preenchidas violam alguma regra do sudoku. Você não precisa resolver o quebra-cabeça. Você só verifica que nenhum dígito se repete em uma linha, uma coluna ou um bloco 3 por 3. Uma passada com três conjuntos de dígitos vistos resolve em O(81), que é constante.
O problema
O tabuleiro é uma grade 9 por 9 de caracteres, cada um um dígito de 1 a 9 ou . para vazio. Retorne true se as células preenchidas seguirem estas regras:
- Cada linha não tem dígito repetido.
- Cada coluna não tem dígito repetido.
- Cada bloco 3 por 3 não tem dígito repetido.
Um tabuleiro pode ser válido mesmo sem ter solução. Só as células preenchidas são verificadas.
Abordagem: três conjuntos por unidade
Mantenha um conjunto de dígitos vistos para cada linha, cada coluna e cada bloco. Para cada célula preenchida, verifique o dígito nos três conjuntos e adicione-o se for novo.
A única parte que exige atenção é o índice do bloco. Para uma célula na linha r e coluna c, o número do bloco é (r // 3) * 3 + c // 3. Ele conta os blocos da esquerda para a direita, de cima para baixo, de 0 a 8.
def is_valid_sudoku(board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for r in range(9):
for c in range(9):
ch = board[r][c]
if ch == ".":
continue
b = (r // 3) * 3 + c // 3
if ch in rows[r] or ch in cols[c] or ch in boxes[b]:
return False
rows[r].add(ch)
cols[c].add(ch)
boxes[b].add(ch)
return True
Traço
Suponha que a linha 0 tenha 5 na coluna 0 e outro 5 na coluna 4. O primeiro 5 é adicionado a rows[0], cols[0] e boxes[0]. Na coluna 4, a verificação ch in rows[0] é verdadeira, então a função retorna false imediatamente. Dígitos iguais no mesmo bloco ou coluna são pegos pelos outros dois conjuntos da mesma forma.
Complexidade
O tabuleiro é sempre 9 por 9, então o tempo é constante, 81 visitas a células. Se você generalizar para um tabuleiro n por n, é O(n ao quadrado) de tempo e O(n ao quadrado) de espaço. Diga os dois, já que os entrevistadores costumam perguntar como isso escala.
Variações que os entrevistadores pedem
| Variação | O que muda |
|---|---|
| Usar menos memória | Armazenar cada unidade como um inteiro de 9 bits e testar bits com 1 << digit |
| Verificar apenas uma jogada | Verificar só a linha, a coluna e o bloco da célula alterada |
| Resolver o sudoku (LeetCode 37) | As mesmas verificações, mais backtracking sobre as células vazias |
| Tabuleiros maiores | O tamanho do bloco vira a raiz quadrada de n, então o índice do bloco usa isso |
A versão com bitmask substitui cada conjunto por um inteiro. mask & (1 << d) testa um dígito e mask |= 1 << d o registra. É mais rápida, mas a versão com conjuntos é mais fácil de acertar sob pressão de tempo, então escreva essa primeiro.
Erros comuns
- Verificar linhas e colunas, mas esquecer os blocos.
- Uma fórmula de bloco errada, como r // 3 + c // 3, que dá o mesmo índice para blocos diferentes.
- Tratar . como um dígito, fazendo duas células vazias contarem como repetição.
- Tentar resolver o tabuleiro quando a questão só pede a validade.
Casos extremos para testar
| Entrada | Esperado |
|---|---|
| Tabuleiro vazio (tudo .) | true |
| Tabuleiro totalmente preenchido e válido | true |
| Repetição só em uma linha | false |
| Repetição só em uma coluna | false |
| Repetição só em um bloco, em linhas e colunas diferentes | false |
| Tabuleiro válido, mas sem solução | true |
Como explicar em uma entrevista
- Reafirme as regras e diga que você só valida, não resolve.
- Nomeie as três unidades e diga que cada uma precisa de um conjunto de vistos.
- Dê a fórmula do índice do bloco e explique com um exemplo.
- Escreva a passada única e o retorno antecipado.
- Declare a complexidade e ofereça a versão com bitmask se pedirem.
Testei o código acima contra uma verificação simples de linha, coluna e bloco em 20.000 tabuleiros aleatórios, alguns válidos e outros deliberadamente quebrados, antes de publicar. Uma verificação aleatória rápida como essa é um bom hábito na hora de praticar.
Prática relacionada
Veja nosso Big O cheat sheet para os termos de complexidade, a lista LeetCode Blind 75 para o que praticar em seguida, e o guia do assistente de entrevista de programação para saber como praticar.
Fale sobre sua abordagem em voz alta enquanto programa. Uma transcrição mostra se você declarou a observação principal antes de escrever. Siga as regras da empresa sobre ferramentas de IA em qualquer avaliação ao vivo.
Pratique entrevistas de programação com YesToTheOffer
Explique sua abordagem em voz alta e depois revise sua transcrição. 30 minutos grátis, sem assinatura.
