Valid Palindrome

Q: Qual é a complexidade de tempo de Valid Palindrome?

As duas abordagens têm complexidade de tempo O(n) , porque cada caractere é examinado um número constante de vezes. A limpeza inicial usa O(n) de memória extra para a cópia. A versão com dois ponteiros usa O(1) de memória extra, pois mantém apenas dois índices.

Q: Como verificar se uma sequência é um palíndromo ignorando caracteres não alfanuméricos?

Mantenha um ponteiro em cada extremidade da string. Mova um ponteiro além de qualquer caractere que não seja uma letra ou um dígito e, quando ambos estiverem sobre letras ou dígitos, compare-os em minúsculas. Se todos os pares comparados corresponderem até os ponteiros se encontrarem, a string é um palíndromo.

Q: Uma string vazia é um palíndromo?

Sim. Um texto vazio é lido da mesma forma nas duas direções, então uma string como ?!-_ , cujos caracteres são todos ignorados, retorna true . Ambas as abordagens fazem isso sem código extra: o texto limpo é igual à sua versão invertida vazia, e os dois ponteiros nunca encontram um par diferente.

Q: Por que usar dois ponteiros em vez de inverter a string?

Inverter requer uma cópia limpa e uma cópia invertida, o que consome O(n) de memória extra. Dois ponteiros comparam os mesmos pares no próprio lugar e podem parar na primeira divergência, muitas vezes após alguns passos. Em entrevistas, geralmente pedem esta versão como pergunta de acompanhamento.

FácilDois ponteiros

+10

Você recebe uma string s. Mantenha apenas as letras e os dígitos, trate letras maiúsculas e minúsculas como iguais e determine se o que restou pode ser lido da mesma forma da esquerda para a direita e da direita para a esquerda. Retorne true se puder e false caso contrário.

Todos os outros caracteres, como ., !, ?, :, ;, - ou _, são ignorados. Se s não tiver nenhuma letra ou dígito, nada restará, e um texto vazio conta como palíndromo.

Função

isPalindrome(s: string) → boolean

sstring: o texto a ser verificado, incluindo a pontuação
Retornaboolean: verdadeiro se as letras e os dígitos de s forem lidos da mesma forma nas duas direções, ignorando maiúsculas e minúsculas

Restrições

1 ≤ s.length ≤ 5 × 10⁴
s contém letras do alfabeto inglês, dígitos e os sinais de pontuação . ! ? : ; - _, sem espaços.

Exemplos

Entrada: s = "Was_it_a_car_or_a_cat_I_saw?"
Saída: true
Explicação: Remova os sublinhados e o ponto de interrogação e passe as letras maiúsculas para minúsculas: você obtém wasitacaroracatisaw, que é igual de trás para frente.

Entrada: s = "race-a-car"
Saída: false
Explicação: Sem os hífens, o texto é raceacar. Lendo da direita, ele começa com raca em vez de race: o e no meio tem um a como seu par espelhado, então a resposta é false.

Entrada: s = "Step-on-no-pets!"
Saída: true
Explicação: O texto mantido é steponnopets. O S maiúsculo corresponde ao s final porque a distinção entre maiúsculas e minúsculas é ignorada, e os hífens e o ! não têm nenhum papel.

+25 testes ocultos ao enviar

Para ir além

Você consegue decidir isso usando memória extra O(1), sem criar uma cópia limpa de s?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

A verificação de palíndromo em si é a conhecida: o primeiro caractere mantido deve ser igual ao último, o segundo deve ser igual ao penúltimo, e assim por diante. O que torna esta versão complicada é que os caracteres que você compara não estão em índices espelhados de s, porque a pontuação está distribuída de maneira desigual nos dois lados. Você pode removê-la primeiro ou deixar dois ponteiros passarem por ela enquanto avançam um em direção ao outro.

Limpe a string e, em seguida, compare-a com sua versão invertida

Intuição

Monte o texto sobre o qual o problema realmente pergunta. Percorra s, mantenha cada letra ou dígito em minúsculas e ignore todo o restante. Para Step-on-no-pets!, isso resulta em steponnopets. Agora a pergunta é a questão simples do palíndromo: esse texto é igual ao seu próprio inverso?

Isso está correto porque a limpeza remove exatamente os caracteres que o problema diz para ignorar e converte para minúsculas as letras cuja caixa o problema diz para ignorar. Se s não contiver letras nem dígitos, o texto limpo ficará vazio, e um texto vazio é igual ao seu inverso, então a resposta é true, sem nenhum caso especial.

Cada caractere é lido uma vez para a limpeza e mais uma vez para a comparação, então o tempo é O(n). A cópia limpa e seu inverso ocupam O(n) de memória extra, que é o custo eliminado pela próxima abordagem.

Algoritmo

Crie um texto vazio cleaned.
Para cada caractere de s, se for uma letra ou um dígito, acrescente-o em minúsculas.
Inverta cleaned.
Retorne se cleaned é igual à sua versão invertida.

def isPalindrome(s):
    cleaned = [ch.lower() for ch in s if ch.isalnum()]
    return cleaned == cleaned[::-1]

Dois ponteiros que ignoram a pontuação

Intuição

A cópia limpa está aí apenas para que você possa comparar caracteres espelhados. Você pode fazer a mesma comparação diretamente em s. Coloque left no primeiro índice e right no último. A cada etapa, se left apontar para um sinal de pontuação, mova-o para a direita; se right apontar para um sinal de pontuação, mova-o para a esquerda. Quando ambos apontarem para letras ou dígitos, compare-os em minúsculas. Uma divergência significa false; uma correspondência significa que ambos os ponteiros avançam para dentro.

Por que essa verificação é igual? Os ponteiros sempre param no próximo caractere mantido de cada extremidade, então visitam os pares (primeiro caractere mantido, último caractere mantido), (segundo caractere mantido, penúltimo caractere mantido) e assim por diante, que são exatamente os pares verificados pela comparação com a sequência invertida. Em Abc-dcbX, o primeiro par é A e X, e a resposta é false após uma comparação.

Cada etapa move pelo menos um ponteiro, e eles param quando se encontram, então o loop é executado no máximo n vezes. Além dos dois índices, nada é armazenado, o que resulta em memória extra O(1).

Algoritmo

Defina left = 0 e right = n-1.
Enquanto left < right: se s[left] não for uma letra nem um dígito, incremente left e continue.
Caso contrário, se s[right] não for uma letra nem um dígito, decremente right e continue.
Caso contrário, compare os dois caracteres em minúsculas. Se forem diferentes, retorne false; se forem iguais, mova ambos os ponteiros para dentro.
Quando os ponteiros se encontrarem, retorne true.

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

Armadilhas e casos extremos

A maioria dos bugs vem dos caracteres que são ignorados e da diferenciação entre maiúsculas e minúsculas.

Comparar s[i] com s[n-1-i] na string original. a-ba é um palíndromo depois que o hífen é removido, mas o espelho de - no índice 1 na string original é b no índice 2.
Mover os dois ponteiros quando apenas um deles está sobre um sinal de pontuação. Ignore um lado de cada vez, ou os dois lados ficarão dessincronizados.
Ignorar sinais de pontuação em um loop interno que ultrapassa o outro ponteiro. Com ?!-_, um loop interno sem limite ultrapassa o fim da string; mantenha a verificação left < right a cada movimento.
Tratar dígitos como ruído. 0P é false: o dígito 0 é mantido e comparado, e não é a letra p.
Retornar false quando nada é mantido. Uma string composta apenas por sinais de pontuação, como ., tem texto limpo vazio, que é um palíndromo.
Uma string composta apenas por dígitos, como 12321, pode chegar ao PHP e ao R como um número. Converta-a primeiro em uma string.

Perguntas frequentes4

Qual é a complexidade de tempo de Valid Palindrome?

As duas abordagens têm complexidade de tempo O(n), porque cada caractere é examinado um número constante de vezes. A limpeza inicial usa O(n) de memória extra para a cópia. A versão com dois ponteiros usa O(1) de memória extra, pois mantém apenas dois índices.

Como verificar se uma sequência é um palíndromo ignorando caracteres não alfanuméricos?

Mantenha um ponteiro em cada extremidade da string. Mova um ponteiro além de qualquer caractere que não seja uma letra ou um dígito e, quando ambos estiverem sobre letras ou dígitos, compare-os em minúsculas. Se todos os pares comparados corresponderem até os ponteiros se encontrarem, a string é um palíndromo.

Uma string vazia é um palíndromo?

Sim. Um texto vazio é lido da mesma forma nas duas direções, então uma string como ?!-_, cujos caracteres são todos ignorados, retorna true. Ambas as abordagens fazem isso sem código extra: o texto limpo é igual à sua versão invertida vazia, e os dois ponteiros nunca encontram um par diferente.

Por que usar dois ponteiros em vez de inverter a string?

Inverter requer uma cópia limpa e uma cópia invertida, o que consome O(n) de memória extra. Dois ponteiros comparam os mesmos pares no próprio lugar e podem parar na primeira divergência, muitas vezes após alguns passos. Em entrevistas, geralmente pedem esta versão como pergunta de acompanhamento.

Python

def isPalindrome(s):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

s = "Was_it_a_car_or_a_cat_I_saw?"

Esperado

true