Edvaldo Torres - Portfolio

Dois Ponteiros

Dois ponteiros é uma técnica em que você usa dois ponteiros que se movem um em direção ao outro ou na mesma direção.

A técnica é frequentemente usada para procurar um par de índices que satisfaça alguma restrição em tempo linear.

Quando:

  • Perguntas sobre strings ou arrays
  • Satisfazer uma restrição
  • "Encontre um conjunto de elementos que satisfaça alguma restrição"
  • Perguntas sobre substring/submatriz

Casos:

  • Dois ponteiros, um começando no início e outro no final, movendo-se um em direção ao outro
  • Um ponteiro movendo-se na mesma direção, um lento e outro rápido.

Palíndromo Válido

Uma frase é um palíndromo se, após converter todas as letras maiúsculas em letras minúsculas e remover todos os caracteres não alfanuméricos, ela for lida da mesma forma de trás para frente. Caracteres alfanuméricos incluem letras e números.

Dado uma string s, retorne verdadeiro se ela for um palíndromo, ou falso caso contrário.

Exemplo 1:

Entrada: s = "A man, a plan, a canal: Panama"
Saída: verdadeiro
Explicação: "amanaplanacanalpanama" é um palíndromo.

Exemplo 2:

Entrada: s = "race a car"
Saída: falso
Explicação: "raceacar" não é um palíndromo.

Exemplo 3:

Entrada: s = " "
Saída: verdadeiro
Explicação: s é uma string vazia "" após remover caracteres não alfanuméricos. Como uma string vazia é lida da mesma forma de trás para frente, é um palíndromo.

Restrições:

  • 1 <= s.length <= 2 * 105
  • s consiste apenas de caracteres ASCII imprimíveis.

Solução

Tente você mesmo
  const isPalindrome = function(s) {

    // transformar string para minúsculas e usar regex para remover não alfanuméricos
    s = s.replace(/[^p{L}p{N}]/giu, '');
    s = s.toLowerCase()

    let a = 0, b = s.length - 1
    
    while(a < b){
      if(s[a] !== s[b]) return false
      a++
      b--
    }
    return true
  };

Explicação:

  1. Livre-se dos valores não alfanuméricos e transforme a string para minúsculas
  2. O ponteiro 'a' aponta para o início da string e o ponteiro 'b' aponta para o final da string
  3. Enquanto 'a' é menor que 'b', se os valores em 'a' e 'b' não forem iguais, retorne falso
  4. Se os valores em 'a' e 'b' forem iguais, incremente 'a' e decremente 'b'
  5. Se o loop terminar, retorne verdadeiro
main*
Go Live