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. Dois índices que começam nas duas extremidades e avançam para o centro fazem isso em uma única passagem.

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

Sim. A verificação com dois ponteiros lê os caracteres no próprio lugar e armazena dois índices, então usa O(1) de espaço extra. Comparar s com sua versão invertida é 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 coddy requer uma comparação.

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

Sim, a leitura é a mesma nas duas direções. No loop de dois ponteiros, left e right começam ambos 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 com 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 nas duas direções

Restrições

1 ≤ s.length ≤ 5 × 10⁴
s contém apenas letras minúsculas do 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.

Para ir além

Como você alteraria os dois ponteiros para ignorar espaços e pontuação e desconsiderar maiúsculas e minúsculas, de modo que Was it a car or a cat I saw seja considerado um palíndromo?

Dicas

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

0 de 3 abertas

Solução

Um palíndromo é igual à sua própria versão invertida, então você pode criar a versão invertida e compará-las. Você não precisa da cópia: o primeiro caractere deve corresponder ao último, o segundo ao penúltimo, e assim por diante. Dois índices que avançam em direção ao centro testam esses pares no próprio lugar e param na primeira divergência.

Compare a string com sua inversa

Intuição

Inverta s e compare: racecar invertida é racecar, e coddy invertida é yddoc. Uma string é lida da mesma forma nos dois sentidos exatamente quando é igual à sua inversa.

O tempo é O(n), mas a cópia invertida ocupa O(n) de espaço extra: 50.000 caracteres para n = 5 × 10^4. O trabalho também é sempre completo: o caso de coddy é decidido pelas primeiras e últimas letras, mas as cinco letras são invertidas primeiro.

Algoritmo

Construa o inverso de s, usando a função de inversão da linguagem ou um loop do último caractere ao primeiro.
Compare o inverso 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 índice i para o índice n-1-i, então s é igual ao seu reverso exatamente quando s[i] é igual a s[n-1-i] para todo i. Cada par aparece duas vezes nessa condição, então basta verificar a metade esquerda. Em racecar, os pares são (0, 6), (1, 5) e (2, 4); o e central no índice 3 não precisa de par.

O primeiro par diferente prova que a resposta é false, então a decisão para coddy é tomada após uma comparação. No máximo n / 2 comparações são executadas, com tempo O(n), e dois índices ocupam espaço O(1). R primeiro 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

Retornar true assim que um par corresponder. abca passa pelo par externo e falha no interno, então true só é retornado após o loop.
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 com == em C. reversed == s compara dois ponteiros e é falso para uma cópia; use strcmp.
Construir a string invertida com result = result + ch. Cada etapa copia a string construída até então: cerca de 1.25 × 10^9 cópias de caracteres para 50.000 letras.
Acessar uma string Swift usando um inteiro como índice: isso não compila. Percorra s.utf8 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. Dois índices que começam nas duas extremidades e avançam para o centro fazem isso em uma única passagem.

Você consegue verificar se uma palavra é um palíndromo sem usar memória extra?

Sim. A verificação com dois ponteiros lê os caracteres no próprio lugar e armazena dois índices, então usa O(1) de espaço extra. Comparar s com sua versão invertida é 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 coddy requer uma comparação.

Um único caractere é um palíndromo?

Sim, a leitura é a mesma nas duas direções. No loop de dois ponteiros, left e right começam ambos no índice 0, o loop nunca é executado e a função retorna true.

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

Teste #1

Teste #2

Teste #3

Argumento

s = "racecar"

Saída Esperada

true