Palindrome String

Q: Como verificar se uma string é um palíndromo?

Compare o primeiro caractere com o último, o segundo com o penúltimo e assim por diante em direção ao meio. Se algum par for diferente, a string não é um palíndromo; se todos os pares corresponderem, é. Dois índices que começam nas duas extremidades e avançam para o centro fazem isso em uma única passagem.

Q: Você consegue verificar um palíndromo sem usar memória extra?

Sim. A verificação com dois ponteiros lê os caracteres diretamente e armazena apenas dois índices, então usa espaço extra O(1) . Comparar s com sua inversão é mais curto de escrever, mas cria uma segunda string de n caracteres.

Q: Qual é a complexidade de tempo para verificar se uma string é um palíndromo?

É O(n) para uma string de comprimento n . A verificação com dois ponteiros faz no máximo n / 2 comparações e para na primeira divergência, então uma string cujos primeiro e último caracteres são diferentes é resolvida após uma comparação.

Q: Um único caractere é um palíndromo?

Sim. Um único caractere é lido da mesma forma nas duas direções, então a resposta é true . No loop de dois ponteiros, left e right começam no índice 0, o loop nunca é executado e a função retorna true .

InicianteDois ponteiros Arrays e strings

+10

Uma string é um palíndromo quando é lida da mesma forma da esquerda para a direita e da direita para a esquerda, como level. Escreva uma função que receba uma string s composta por letras minúsculas do alfabeto inglês e retorne true se s for um palíndromo e false caso contrário.

Função

isPalindrome(s: string) → boolean

sstring: a string em letras minúsculas a ser verificada
Retornaboolean: verdadeiro quando s é lido da mesma forma em ambas as direções

Restrições

1 ≤ s.length ≤ 5 × 10⁴
s contém apenas letras minúsculas do alfabeto inglês (a a z).

Exemplos

Entrada: s = "racecar"
Saída: true
Explicação: Compare de fora para dentro: r com r, a com a, c com c. O e do meio não tem par e não precisa de um, então a resposta é true.

Entrada: s = "abba"
Saída: true
Explicação: Com um comprimento par, cada letra tem um par: os dois as combinam e os dois bs combinam, então a resposta é true.

Entrada: s = "coddy"
Saída: false
Explicação: A primeira letra c e a última letra y já são diferentes, então coddy não é um palíndromo e a resposta é false.

+16 testes ocultos ao enviar

Para ir além

Uma frase como Was it a car or a cat I saw é um palíndromo quando se ignoram maiúsculas e minúsculas, espaços e pontuação. Como você alteraria os dois ponteiros para pular esses caracteres?

Dicas

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

0 de 3 abertas

Solução

Um palíndromo é igual ao seu inverso, então a verificação direta constrói o inverso e faz a comparação. A verificação melhor não constrói nada: o primeiro caractere deve corresponder ao último, o segundo ao penúltimo, e assim por diante em direção ao meio. Dois índices que avançam para dentro testam esses pares no próprio lugar e param na primeira divergência.

Compare a string com sua reversa

Intuição

Ler s da mesma forma nas duas direções significa que s é igual ao seu inverso. Então, inverta-a e compare: racecar invertida é racecar, e coddy invertida é yddoc, que é diferente.

Construir o inverso e comparar cada um percorre cada caractere uma vez, então o tempo é O(n). A cópia invertida contém mais n caracteres, o que representa espaço extra O(n): quando n = 5 × 10^4, são 50.000 caracteres criados apenas para serem comparados e descartados.

Isso também faz todo o trabalho sempre. A resposta para coddy é determinada pelas letras inicial e final, mas essa abordagem inverte os cinco caracteres antes de verificar.

Algoritmo

Crie a versão invertida de s usando a função de inversão da linguagem ou um loop do último caractere ao primeiro.
Compare a versão invertida com s.
Retorne true se forem iguais e false caso contrário.

def isPalindrome(s):
    return s == s[::-1]

Dois ponteiros, um em cada extremidade

Intuição

Inverter move o caractere no índice i para o índice n-1-i, então s é igual à sua inversa exatamente quando s[i] é igual a s[n-1-i] para todo i. Cada par aparece duas vezes nessa lista, então verifique apenas a metade esquerda. Coloque left no índice 0 e right no índice n-1, compare os dois caracteres e mova os dois ponteiros um passo para dentro.

Pare quando os ponteiros se encontrarem ou se cruzarem. Em racecar, eles verificam os pares de índices (0, 6), (1, 5) e (2, 4), depois se encontram no índice 3, o e do meio, que não precisa de par. Em abba, eles verificam (0, 3) e (1, 2) e depois se cruzam. O primeiro par diferente prova que a resposta é false, então retorne imediatamente: o resultado de coddy é determinado após uma comparação.

Acontecem no máximo n / 2 comparações, o que corresponde a O(n) de tempo, e a única memória usada são dois índices, O(1) de espaço. R é a exceção: primeiro, ele lê a string como um vetor de códigos de caracteres, o que custa O(n).

Algoritmo

Defina left = 0 e right = n-1.
Enquanto left < right, compare s[left] com s[right].
Se forem diferentes, retorne false.
Caso contrário, some 1 a left, subtraia 1 de right e repita.
Quando os ponteiros se encontrarem ou se cruzarem, todos os pares corresponderão: retorne true.

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

Armadilhas e casos extremos

O loop é curto, então os erros estão nos limites e nas instruções de retorno.

Retornar true assim que um par corresponder. abca passa pelo par externo e falha no interno, então true só pode ser retornado depois que o loop terminar.
Começar right em n em vez de n-1, o que acessa uma posição além do fim (em C, o '\0' terminador). Em Lua e R, os índices vão de 1 a n, então, nesses casos, right começa em n.
Comparar strings pelo endereço. Em C, reversed == s compara dois ponteiros e é sempre falso para uma cópia recém-criada; use strcmp.
Construir a string invertida com result = result + ch em um loop. Cada etapa copia toda a string construída até então, totalizando cerca de 1.25 × 10^9 cópias de caracteres para 50,000 letras.
Indexar uma string Swift com um inteiro. Isso não compila; percorra s.utf8 usando os próprios índices ou copie os caracteres para um array.

Perguntas frequentes4

Como verificar se uma string é um palíndromo?

Compare o primeiro caractere com o último, o segundo com o penúltimo e assim por diante em direção ao meio. Se algum par for diferente, a string não é um palíndromo; se todos os pares corresponderem, é. Dois índices que começam nas duas extremidades e avançam para o centro fazem isso em uma única passagem.

Você consegue verificar um palíndromo sem usar memória extra?

Sim. A verificação com dois ponteiros lê os caracteres diretamente e armazena apenas dois índices, então usa espaço extra O(1). Comparar s com sua inversão é mais curto de escrever, mas cria uma segunda string de n caracteres.

Qual é a complexidade de tempo para verificar se uma string é um palíndromo?

É O(n) para uma string de comprimento n. A verificação com dois ponteiros faz no máximo n / 2 comparações e para na primeira divergência, então uma string cujos primeiro e último caracteres são diferentes é resolvida após uma comparação.

Um único caractere é um palíndromo?

Sim. Um único caractere é lido da mesma forma nas duas direções, então a resposta é true. No loop de dois ponteiros, left e right começam no índice 0, o loop nunca é executado e a função retorna true.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

s = "racecar"

Esperado

true