24 de Março
Palíndromo válido
Como perceber que o problema pede comparação simetrica e não uma pilha de etapas desnecessarias.
Strings e Dois Ponteiros Iniciante 12 min TypeScript
Dada uma string s, retorne true se ela for um palindromo considerando apenas caracteres alfanumericos e ignorando diferencas entre maiusculas e minusculas.
Exemplo:
Input: s = "A man, a plan, a canal: Panama"
Output: true
O que perceber antes de codar
- Espacos, pontuacao e simbolos devem ser ignorados.
- Comparação de palindromo sempre acontece do lado de fora para dentro.
- Normalizar para lowercase evita falso negativo por causa de maiuscula.
Erros comuns
- esquecer de pular caracteres não alfanumericos antes de comparar
- limpar a string inteira sem perceber que a mesma resposta sai com [O(1)](/pt-br/glossario/o-um) de memória extra
Passo 1 — Entender o que deve ser ignorado
Se você comparar a string crua, vai errar.
O problema manda ignorar:
- espacos
- pontuacao
- diferença entre maiusculas e minusculas
Entao a pergunta real não e "a string original e igual ao reverso?".
A pergunta real e:
depois de ignorar o que não importa, o início bate com o fim?
Passo 2 — Escrever a primeira versão correta
Uma versão inicial simples e montar uma versão limpa da string e comparar com o reverso:
export function isPalindrome(s: string): boolean {
const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '')
return cleaned === cleaned.split('').reverse().join('')
}
Funciona. Mas cria uma string nova e ainda cria outra para o reverso.
Passo 3 — Perguntar o que realmente precisa ser comparado
Palindromo e sempre comparação simetrica:
- primeiro com ultimo
- segundo com penultimo
- e assim por diante
Isso já sugere dois ponteiros.
Passo 4 — Limpar sob demanda
Em vez de limpar tudo antes, você pode pular caracteres inválidos na hora.
Assim:
leftanda para a direitarightanda para a esquerda- ambos ignoram o que não for alfanumerico
- quando param, você compara os dois
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function isPalindrome(s: string): boolean {
// sua solução aqui
return false
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n)
Espaço: O(1)
Solução 1 — Limpar e comparar O(n) com memória extra
Essa e uma boa versão inicial.
export function isPalindrome(s: string): boolean {
const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '')
return cleaned === cleaned.split('').reverse().join('')
}Simples. Mas usa memória desnecessaria.
Solução 2 — Dois ponteiros O(n) e O(1) de memória extra
Se a comparação e do lado de fora para dentro, use dois ponteiros e pule o que não interessa.
function isAlphaNumeric(char: string): boolean {
return /[a-z0-9]/i.test(char)
}
export function isPalindrome(s: string): boolean {
let left = 0
let right = s.length - 1
while (left < right) {
while (left < right && !isAlphaNumeric(s[left])) {
left += 1
}
while (left < right && !isAlphaNumeric(s[right])) {
right -= 1
}
if (s[left].toLowerCase() !== s[right].toLowerCase()) {
return false
}
left += 1
right -= 1
}
return true
}Você compara só o que importa e usa a própria string original como fonte.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial limpa a string e compara com o reverso, o que funciona em
O(n)mas usa memória extra. Como palindromo e uma comparação simetrica, eu posso usardois ponteiros, pular caracteres inválidos na hora e manterO(1)de memória extra.
Isso mostra que você:
- entendeu a versão simples primeiro
- transformou a regra do problema em movimento de ponteiros
- justificou a melhora sem complicar a implementação
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- comparar extremos
- caminhar para o centro
- ignorar parte da entrada durante a leitura
- validar simetria sem criar estruturas novas
O ponto não e decorar “palindromo =
dois ponteiros”.
O ponto e perceber quando o problema já te empurra para comparar bordas.