Guerra de lenguajes
Python, PHP, Javascript (Nodejs)
Subcadena palindrómica más larga

Guerra de lenguajes Python, PHP, Javascript (Nodejs) Subcadena palindrómica más larga

Carlos Rivas's photo
Carlos Rivas
·Apr 23, 2021·

5 min read

Play this article

Que tal amigos, un nuevo post de esta guerra pero esta vez en español, No se cual es mejor, pero voy a tratar de descubrirlo. Espero disfruten esta serie ahora en español.

Este es un reto de leetcode.com, hice este reto en Python3, y luego en PHP y Javascript.

Problema:

Dado una cadena de texto s, devuelve la subcadena palindrómica más larga en s.

Ejemplo 1:

Entrada: s = "babad" Salida: "bab" Nota: "aba" es una respuesta válida.

Tengo que decirles que use un super poder llamado google ;) para descubrir como obtener de un string una parte palindrómica. Aquí los detalles en.wikipedia.org/wiki/Longest_palindromic_s..

Primero, Necesito una longitud impar para obtener una cadena palindrómico, la documentación que conseguí recomienda usar un símbolo.

Entonces, Voy a explicarlo en cada lenguaje, ¡aquí vamos!

Python

Primero, necesito agregar un símbolo, yo use el método "while" para agregar el símbolo entre las letras, voy a recorrer la cadena como un diccionario, tenia que validar si a la derecha y a la izquierda existía la misma letra o símbolo para aumentar la variable "radius". Si "radius" es mayor que la variable "palindrome", actualizo la variable y asigno el valor a la variable "maxCenter", al final, obtengo el mínimo y el máximo de la cadena para obtener la cadena palindrómica.

class Solution:
  def longestPalindrome(self, s: str):
    c = 0
    ss = '|'
    while (c < len(s)):
      ss = ss + s[c] + '|'
      c += 1

    palindrome = 0

    center = 0
    maxCenter = 0
    while (center < len(ss)):
      radius = 0

      while (
          center - (radius + 1) >= 0 and
          center + (radius + 1) < len(ss) and
          ss[center - (radius + 1)] == ss[center + (radius + 1)]
      ):
        radius = radius + 1

      if radius > palindrome:
        palindrome = radius
        maxCenter = center

      center = center + 1

    r = ''

    minimum = maxCenter - palindrome
    maximum = maxCenter + palindrome
    while (minimum <= maximum):
        if (ss[minimum] != '|'):
          r = r + ss[minimum]

        minimum += 1

    return r


sol = Solution()
result = sol.longestPalindrome('book')
print(result)

PHP

Primero, necesito agregar un símbolo, pero en PHP no puedo usar una cadena como un arreglo, tengo que transformar la cadena en arreglo con el método "str_split", Use el método "while" para agregar el símbolo entre las letras en el arreglo, recorro el arreglo y luego tengo que validar si a la derecha y a la izquierda existe la misma letra o símbolo, si existe incremento la variable "radius". Si "radius" es mayor que la variable "palindrome", actualizo la variable y asigno la variable "maxCenter", al final, obtengo el mínimo y el máximo de la cadena para obtener la cadena palindrómica.

<?php
class Solution
{
    public function longestPalindrome($s)
    {
        $c  = 0;
        $s  = str_split($s);
        $ss = ['|'];
        while ($c < count($s)) {
            $ss[] = $s[$c];
            $ss[] = '|';
            $c++;
        }
        $palindrome = 0;
        $center     = 0;
        $maxCenter  = 0;

        while ($center < count($ss)) {
            $radius = 0;

            while (
                $center - ($radius + 1) >= 0 &&
                $center + ($radius + 1) < count($ss) &&
                $ss[$center - ($radius + 1)] == $ss[$center + ($radius + 1)]
            ) {
                $radius = $radius + 1;
            }

            if ($radius > $palindrome) {
                $palindrome = $radius;
                $maxCenter  = $center;
            }

            $center = $center + 1;
        }
        $r   = '';
        $min = $maxCenter - $palindrome;
        $max = $maxCenter + $palindrome;
        while ($min <= $max) {
            if ($ss[$min] !== '|') {
                $r = $r . $ss[$min];
            }
            $min += 1;
        }

        return $r;
    }
}

$sol    = new Solution();
$result = $sol->longestPalindrome('book');
var_dump($result);
?>

Javascript

Primero, necesito agregar un símbolo, yo use el método "while" para agregar el símbolo entre las letras, voy a recorrer la cadena como un diccionario, tenia que validar si a la derecha y a la izquierda existía la misma letra o símbolo para aumentar la variable "radius". Si "radius" es mayor que la variable "palindrome", actualizo la variable y asigno el valor a la variable "maxCenter", al final, obtengo el mínimo y el máximo de la cadena para obtener la cadena palindrómica.

class Solution {
  longestPalindrome(s) {
    let c = 0;
    let ss = '|';
    while (c < s.length) {
      ss = ss + s[c] + '|';
      c++;
    }

    let palindrome = 0;

    let center = 0;
    let maxCenter = 0;
    while (center < ss.length) {
      let radius = 0;

      while (
        center - (radius + 1) >= 0 &&
        center + (radius + 1) < ss.length &&
        ss[center - (radius + 1)] == ss[center + (radius + 1)]
      ) {
        radius = radius + 1;
      }

      if (radius > palindrome) {
        palindrome = radius;
        maxCenter = center;
      }

      center = center + 1;
    }
    let r = '';

    let min = maxCenter - palindrome;
    let max = maxCenter + palindrome;
    while (min <= max) {
      if (ss[min] !== '|') {
        r = r + ss[min];
      }
      min += 1;
    }
    return r;
  }
}

const sol = new Solution();
const result = sol.longestPalindrome('book');
console.log(result);

Conclusion

  • Estructura: Pueden ver que en Python tuve que cambiar el nombre de la variable "min" a "minimum" y "max" a "maximum" porque en Python existen estas palabras como métodos, en PHP tuve que cambiar la cadena a arreglo.
  • Lineas: Python: 44, PHP: 53, Javascript: 48
  • Tiempo de ejecución: Python: 4336 ms, PHP: 832 ms, Javascript: 144 ms
  • Memoria usada: Python: 14.3 MB, PHP: 15.9 MB, Javascript: 44.9 MB

¿Les gustaría que escriba mas retos en español? Estaré pendiente de sus comentarios.

Espero que disfruten mi post y recuerden solo soy un Dev like you!

 
Share this