Soluciones LeetCode
#14 — Máximo prefijo común.

Planteamiento del problema

Escribe una función para encontrar la cadena de prefijo común más larga entre un arreglo de cadenas.

Si no hay un prefijo común, devuelve una cadena vacía "".

Ejemplo 1:

Ejemplo 2:

Restricciones:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consiste solo de letras minúsculas del inglés si no está vacía.

La manera ingenua — escaneo horizontal

El enfoque más intuitivo es tomar la primera cadena como prefijo candidato y luego iterar sobre las cadenas restantes. Para cada palabra subsiguiente, acortamos el candidato hasta que se convierta en prefijo de esa palabra. Esto se llama escaneo horizontal porque nos movemos de izquierda a derecha a través del arreglo, comparando el prefijo con cada cadena horizontalmente.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 1:
            return strs[0]          # Solo una cadena → es el prefijo
        
        prefix = strs[0]
        
        for i in range(1, len(strs)):
            # Seguir acortando el prefijo hasta que coincida con el inicio de strs[i]
            while strs[i].find(prefix) != 0:
                prefix = prefix[:-1]   # Eliminar el último carácter
                if not prefix:
                    return ""          # No hay prefijo común
        return prefix
            

Tracemos el ejemplo strs = ["flower","flow","flight"]:

Este método es directo pero puede realizar comparaciones redundantes. En el peor de los casos, podríamos terminar acortando el prefijo carácter por carácter para cada cadena, lo que lleva a un tiempo O(S) donde S es la suma de todos los caracteres en todas las cadenas. El espacio auxiliar es O(1).

Un ángulo diferente — escaneo vertical

En lugar de comparar palabras completas, podemos escanear carácter por carácter verticalmente. Tomamos el primer carácter de la primera cadena y lo comparamos con el primer carácter de cada una de las otras cadenas. Si todos coinciden, pasamos al segundo carácter, y así sucesivamente. En el momento en que encontramos una discrepancia o llegamos al final de alguna cadena, nos detenemos y devolvemos el prefijo construido hasta el momento.

Este enfoque puede ser más eficiente en casos donde el prefijo común es corto o ocurre una discrepancia temprana, porque evitamos mirar el resto de las cadenas.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 1:
            return strs[0]
        
        # Escanear caracteres de la primera cadena
        for i in range(len(strs[0])):
            ch = strs[0][i]
            # Comparar con cada otra cadena en la posición i
            for j in range(1, len(strs)):
                # Detenerse si excedemos la longitud o encontramos una discrepancia
                if i == len(strs[j]) or strs[j][i] != ch:
                    return strs[0][:i]
        
        # Todos los caracteres de la primera cadena coincidieron en las demás
        return strs[0]
            

Tracemos strs = ["flower","flow","flight"] con escaneo vertical:

La complejidad temporal sigue siendo O(S) en el peor caso (cuando todas las cadenas son idénticas), pero a menudo realiza menos comparaciones de caracteres. El espacio permanece O(1).

Divide y vencerás

Este problema también se presta muy bien a una estrategia recursiva de divide y vencerás. La idea: dividir el arreglo en dos mitades, encontrar el LCP de cada mitad recursivamente y luego encontrar el LCP de esos dos resultados. Esta es una aplicación clásica del paradigma y puede ser útil cuando queremos paralelizar o cuando el arreglo es grande.

La función auxiliar lcp(izquierda, derecha) encuentra el prefijo común entre dos cadenas usando un escaneo vertical, y divide_y_venceras divide recursivamente el arreglo.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def lcp(izquierda: str, derecha: str) -> str:
            """Devuelve el prefijo común de dos cadenas."""
            min_long = min(len(izquierda), len(derecha))
            for i in range(min_long):
                if izquierda[i] != derecha[i]:
                    return izquierda[:i]
            return izquierda[:min_long]

        def divide_y_venceras(arr, l, r):
            """Encuentra recursivamente el LCP en arr[l..r]."""
            if l == r:
                return arr[l]
            medio = (l + r) // 2
            lcp_izq = divide_y_venceras(arr, l, medio)
            lcp_der = divide_y_venceras(arr, medio + 1, r)
            return lcp(lcp_izq, lcp_der)

        return divide_y_venceras(strs, 0, len(strs) - 1)
            

Traza para strs = ["flower","flow","flight"]:

La relación de recurrencia para la complejidad temporal es T(n) = 2·T(n/2) + O(m), donde m es la longitud de las cadenas. En el peor caso, esto todavía resulta en O(S) comparaciones totales de caracteres. Sin embargo, el enfoque de divide y vencerás tiene la ventaja de ser fácilmente paralelizable y demuestra un patrón algorítmico poderoso.

Optimizando aún más — búsqueda binaria

¿Podemos hacerlo mejor que los escaneos lineales? Si consideramos la longitud del prefijo común, está limitada por la longitud de la cadena más corta. Podemos realizar una búsqueda binaria en la posible longitud del prefijo. Para una longitud candidata mid, verificamos si los primeros mid caracteres de la primera cadena forman un prefijo común válido para todas las cadenas. Si es así, intentamos una longitud más larga; si no, intentamos una más corta.

Este enfoque reduce el número de comparaciones en muchos escenarios, especialmente cuando las cadenas son largas y el prefijo es relativamente corto o largo. La verificación en sí (esLCP(mid)) itera sobre las cadenas, haciendo que el tiempo total sea O(S·log m) donde m es la longitud de la cadena más corta. Esto puede ser más rápido que el escaneo lineal en la práctica.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def esLCP(longitud: int) -> bool:
            """Verifica si los primeros `longitud` caracteres de strs[0] son comunes."""
            prefijo = strs[0][:longitud]
            for s in strs[1:]:
                if not s.startswith(prefijo):
                    return False
            return True

        if len(strs) == 1:
            return strs[0]

        bajo, alto = 0, min(len(s) for s in strs)
        while bajo <= alto:
            mid = (bajo + alto) // 2
            if esLCP(mid):
                bajo = mid + 1      # Intentar un prefijo más largo
            else:
                alto = mid - 1      # Intentar uno más corto

        return strs[0][:alto]
            

Traza de búsqueda binaria para strs = ["flower","flow","flight"] donde la longitud más corta es 4 ("flow"):

La solución de búsqueda binaria reduce elegantemente la longitud del prefijo. La complejidad espacial es O(1), y la verificación startswith utiliza una comparación eficiente de subcadenas.

Comparación final de complejidades

Los cuatro enfoques son correctos y funcionan dentro de las restricciones del problema. Aquí un resumen rápido:

• Escaneo horizontal: tiempo O(S), espacio O(1). Simple pero puede hacer trabajo extra.
• Escaneo vertical: tiempo O(S), espacio O(1). A menudo se detiene temprano.
• Divide y vencerás: tiempo O(S), espacio O(m·log n) por la pila de recursión (o O(1) iterativo). Demuestra recursión.
• Búsqueda binaria: tiempo O(S·log m), espacio O(1). Puede ser más rápida cuando las cadenas son largas y la longitud del prefijo es extrema.

En una entrevista, los métodos de escaneo vertical o búsqueda binaria son particularmente apreciados por su eficiencia y claridad.

Referencias y lecturas adicionales

• Página del problema LeetCode Longest Common Prefix — problema oficial y foros de discusión.
• Wikipedia: LCP array (en inglés) — concepto relacionado en arreglos de sufijos.
• Wikipedia: Algoritmo divide y vencerás — el paradigma detrás de la solución recursiva.
• Real Python: Strings and Character Data in Python (en inglés) — inmersión profunda en operaciones con cadenas como startswith().

¿No te cansas de lumænaut? Lee esto...

• Capítulo 2 | Todo lo que no sé sobre bloguear — la bitácora detrás del sitio: dominios, SEO, plugins y aprender en público.
• Los 8 paradigmas de algoritmos — ocho modelos mentales que reutilizarás en problemas, entrevistas y código de producción.
• Cómo funciona el Game Loop — el latido del corazón de un juego: actualizar, renderizar y temporización constante en lenguaje sencillo.