Palíndromo após uma remoção
A missão
Problema
Um jogo de palavras aceita uma string se ela for lida da mesma forma de frente para trás e de trás para a frente, e perdoa um único erro de digitação. Dada uma string s de letras minúsculas, retorne True se s já for um palíndromo ou virar um depois de remover exatamente um caractere, e False caso contrário. A string vazia conta como palíndromo.
Exemplos
Input: s = "racexcar"
Output: True
Por quê: remover o x deixa "racecar"
Input: s = "abcda"
Output: False
Por quê: depois que os a das pontas coincidem, b e d divergem, e remover qualquer um dos dois ainda falha
Input: s = ""
Output: True
Por quê: edge case: não há nada para comparar, então nenhuma remoção é necessária
Dicas
0 / 3
Testar toda remoção possível e verificar cada resultado é quadrático. A maior parte da string nunca precisa de uma segunda olhada.
Percorra a string com dois ponteiros (two pointers), das duas pontas para o meio. Enquanto os caracteres coincidirem, nenhuma decisão é necessária. O único momento interessante é a primeira divergência.
Na primeira divergência, o caractere removido precisa ser um dos dois sob os ponteiros. Verifique se o trecho interno sem o da esquerda, ou sem o da direita, é um palíndromo por si só. Se os ponteiros se encontrarem sem nenhuma divergência, a resposta já é sim.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Restrições
- s holds lowercase letters
- the empty string counts as a palindrome
Solução
Caracteres externos que coincidem nunca são o problema, então os dois ponteiros passam por eles sem gastar a única remoção. Na primeira divergência, qualquer correção precisa remover um desses dois caracteres, já que todo caractere fora deles já tem o seu par. Isso deixa exatamente duas substrings candidatas, cada uma verificada com uma varredura simples de palíndromo, e nenhuma outra escolha aparece dentro delas. O tempo é O(n), porque cada caractere é comparado no máximo algumas vezes, e o espaço é O(1).
def almost_palindrome(s):
def is_pal(i, j): # plain two-pointer check of s[i..j]
while i < j:
if s[i] != s[j]:
return False
i, j = i + 1, j - 1
return True
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
# the one deletion must remove s[i] or s[j]
return is_pal(i + 1, j) or is_pal(i, j - 1)
i, j = i + 1, j - 1
return True
print(almost_palindrome("racexcar")) # -> True
print(almost_palindrome("abcda")) # -> False
print(almost_palindrome("")) # -> TrueTravou na ideia, e não no código? Valid Palindrome explica isso.