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

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!

No Comments Yet