Pular para o conteúdo

Valid Palindrome

Aula 2 de 11 · 4 min

Valid Palindrome

Passo 1 de 7

Um palíndromo se lê igual nos dois sentidos, então leia pelas duas pontas ao mesmo tempo: sem cópia invertida.

A ideia

Um palíndromo se lê igual pelas duas pontas, então confira pelas duas pontas. Ponha um ponteiro no início, outro no fim, e ande com os dois um em direção ao outro.

Uma diferença é um não definitivo. Encontrar-se no meio é um sim definitivo — sem cópia invertida, sem memória extra.

Exemplo do mundo real

Verificadores de código de barras e de número de conta fazem o mesmo tipo de teste: leem pela frente e por trás ao mesmo tempo e desistem no instante em que os dois lados discordam. Varrer o código inteiro primeiro e só depois comparar desperdiça a metade do trabalho que você já sabia que estava perdida.

O código

Sua vez

Preencha a lacuna.

def is_palindrome(s):
  left, right = 0, len(s) - 1
  while ___:
      if s[left] != s[right]:
          return False
      left, right = left + 1, right - 1
  return True

print(is_palindrome("abba"), is_palindrome("abca"))   # want True False

Mini quiz

1 / 3

Quanto custa a verificação de palíndromo com dois ponteiros (two pointers)?