O desafio de encontrar o maior prefixo compartilhado por um conjunto de strings é clássico em entrevistas e competições. Abaixo, exploramos cinco abordagens distintas em Python, cada uma com suas próprias características de desempenho e clareza.

1. Explorando a Ordenação Lexicográfica

Quando ordenamos alfabeticamente, a primeira e a última palavra naturalmente concentram as diferenças extremas. Comparando apenas essas duas, extraímos o prefixo comum.

from typing import List

class LexicographicPrefix:
    def longest_prefix(self, words: List[str]) -> str:
        if not words:
            return ""
        left, right = min(words), max(words)
        for idx, char in enumerate(left):
            if char != right[idx]:
                return right[:idx]
        return left

demo = LexicographicPrefix()
print("Resultado:", demo.longest_prefix(["flor", "fluir", "flamejar", "flauta"]))

2. Varredura Horizontal (ou Redução Progressiva)

Consiste em ir "esticando" o prefixo candidato, comparando-o com cada nova palavra da lista.

class HorizontalScan:
    def longest_prefix(self, words: List[str]) -> str:
        if not words:
            return ""
        prefix = words[0]
        for w in words[1:]:
            prefix = self._match(prefix, w)
            if not prefix:
                break
        return prefix

    @staticmethod
    def _match(a: str, b: str) -> str:
        lim = min(len(a), len(b))
        k = 0
        while k < lim and a[k] == b[k]:
            k += 1
        return a[:k]

print("Horizontal:", HorizontalScan().longest_prefix(["codar", "código", "cofre", "coisa"]))

Análise: Tempo O(m·n), espaço O(1).

3. Varredura Vertical (Caractere por Caractere)

Aqui, percorremos cada coluna (posição) simultaneamente em todas as palavras, parando no primeiro desencontro.

class VerticalScan:
    def longest_prefix(self, words: List[str]) -> str:
        if not words:
            return ""
        for col in range(len(words[0])):
            ch = words[0][col]
            for row in range(1, len(words)):
                if col == len(words[row]) or words[row][col] != ch:
                    return words[0][:col]
        return words[0]

print("Vertical:", VerticalScan().longest_prefix(["dado", "dados", "dança", "dardo"]))

Análise: Tempo O(m·n), espaço O(1).

4. Divisão e Conquista

Recursivamente dividimos o vetor ao meio, calculamos prefixos locais e combinamos os resultados.

class DivideConquer:
    def longest_prefix(self, words: List[str]) -> str:
        if not words:
            return ""
        return self._solve(words, 0, len(words) - 1)

    def _solve(self, words: List[str], l: int, r: int) -> str:
        if l == r:
            return words[l]
        mid = (l + r) // 2
        left_p = self._solve(words, l, mid)
        right_p = self._solve(words, mid + 1, r)
        return self._merge(left_p, right_p)

    def _merge(self, a: str, b: str) -> str:
        limit = min(len(a), len(b))
        for i in range(limit):
            if a[i] != b[i]:
                return a[:i]
        return a[:limit]

print("D&C:", DivideConquer().longest_prefix(["letras", "leitura", "leve"]))

Análise: Tempo O(m·n), espaço O(m log n) devido à pilha de recursão.

5. Busca Binária no Comprimento do Prefixo

Limitamos a busca entre 0 e o tamanho da menor palavra. A cada iteração, verificamos se todas as strings compartilham o prefixo de tamanho mid.

class BinarySearchPrefix:
    def longest_prefix(self, words: List[str]) -> str:
        if not words:
            return ""
        low, high = 0, min(map(len, words))

        def is_common(k: int) -> bool:
            lead = words[0][:k]
            return all(w.startswith(lead) for w in words[1:])

        while low < high:
            mid = (low + high + 1) // 2
            if is_common(mid):
                low = mid
            else:
                high = mid - 1
        return words[0][:low]

print("Binary:", BinarySearchPrefix().longest_prefix(["estrutura", "estrela", "estresse"]))

Análise: Tempo O(m·n log m), espaço O(1).

Escolher a técnica depende do tamanho do conjunto, padrões de entrada e restrições de memória. Em geral, a varredura vertical é a mais direta, enquanto a busca binária pode ser vantajosa quando as strings são muito longas.