Palíndromo ignorando a pontuação
A missão
Problema
Decida se uma string se lê igual de frente para trás e de trás para frente quando você ignora maiúsculas e minúsculas e pula todo caractere que não é letra nem dígito. Escreva primeiro uma função recursiva que compara as duas pontas e chama a si mesma sobre o que fica entre elas; depois, transforme-a em um loop que lida com strings de qualquer tamanho.
Exemplos
Input: s = "A man, a plan, a canal: Panama"
Output: True
Por quê: só as letras formam amanaplanacanalpanama nos dois sentidos
Input: s = "race a car"
Output: False
Por quê: raceacar invertido é racaecar
Input: s = ".,!"
Output: True
Por quê: edge case: nada sobra depois de pular a pontuação, e uma string vazia é um palíndromo
Dicas
0 / 3
Olhe para o par de caracteres mais externo. Se algum deles for pontuação, descarte-o e faça a mesma pergunta de novo. Se os dois contam e são diferentes, a resposta é não.
Passe dois índices, i a partir da esquerda e j a partir da direita, em vez de fatiar a string, para que cada chamada seja O(1). O caso base é i >= j.
Cada chamada recursiva é a última coisa que a função faz, com o resultado retornado sem mudança, então ela é uma chamada de cauda. O Python guarda todos os frames mesmo assim; por isso, reescreva a função como um loop while que atualiza i e j onde antes ficavam as chamadas.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Solução
A versão recursiva expressa a definição diretamente: pule uma ponta não alfanumérica, retorne falso se o par divergir e, caso contrário, mova as duas pontas para dentro. Toda chamada recursiva está em posição de cauda, já que o resultado dela é retornado sem mudança e sem trabalho restante; assim, o frame que fez a chamada é peso morto. O Python não reaproveita esses frames, então uma string de alguns milhares de caracteres estoura o limite de recursão, mesmo com a lógica correta. O loop é a tradução mecânica: os parâmetros i e j viram variáveis, e cada chamada de cauda vira uma atualização deles seguida de mais uma volta no loop. As duas rodam em tempo O(n); a recursiva usa O(n) de pilha, e o loop, O(1).
def is_palindrome(s, i=0, j=None):
if j is None:
j = len(s) - 1
if i >= j:
return True
if not s[i].isalnum():
return is_palindrome(s, i + 1, j)
if not s[j].isalnum():
return is_palindrome(s, i, j - 1)
if s[i].lower() != s[j].lower():
return False
return is_palindrome(s, i + 1, j - 1) # tail call: nothing happens after it
def is_palindrome_loop(s):
i, j = 0, len(s) - 1
while i < j: # each tail call becomes one update
if not s[i].isalnum():
i += 1
elif not s[j].isalnum():
j -= 1
elif s[i].lower() != s[j].lower():
return False
else:
i, j = i + 1, j - 1
return True
print(is_palindrome("A man, a plan, a canal: Panama")) # -> True
print(is_palindrome("race a car")) # -> False
print(is_palindrome(".,!")) # -> True
print(is_palindrome_loop("ab" * 50000 + "a")) # -> TrueTravou na ideia, e não no código? Chamadas de cauda e loops explica isso.