Published on

LeetCode Easy 14: Longest Common Prefix em Python

Authors

Neste post, o problema 14 do LeetCode, Longest Common Prefix, é resolvido em Python de quatro formas. O post faz parte da série LeetCode Easy, que traz toda sexta um problema de nível fácil (Easy), da solução mais simples até a mais eficiente. O post anterior tratou do problema 13, o Roman to Integer. Cada versão tem código comentado e testado, com a análise de complexidade em notação Big O. Os posts ficam reunidos na tag leetcode-easy.

O problema

O Longest Common Prefix recebe uma lista de palavras strs e pede o maior prefixo comum a todas elas. Prefixo é o começo da palavra. Em "flower", "flow" e "flight", as três começam com "fl", e a resposta é "fl". Se as palavras não têm nenhum começo em comum, como "dog", "racecar" e "car", a resposta é o texto vazio "".

O enunciado garante que a lista tem de 1 a 200 palavras, que cada palavra tem de 0 a 200 letras e que só aparecem letras minúsculas do inglês.

Dois quadros. À esquerda, as palavras flower, flow e flight, uma por linha, com as letras f e l das três destacadas em verde dentro de um retângulo tracejado. À direita, as palavras dog, racecar e car, sem nenhuma letra destacada, porque não têm começo em comum

Figura 1. Os dois exemplos do enunciado. Em verde, o começo que todas as palavras dividem. Elaborado para este post.

Big O em poucas palavras

A notação Big O descreve como o custo de um algoritmo cresce quando a entrada cresce. Neste problema, a entrada tem duas medidas. A primeira é n, a quantidade de palavras. A segunda é m, o tamanho das palavras. Também aparece p, o tamanho do prefixo comum, que nunca passa de m. O(n·m) quer dizer que o trabalho cresce na proporção do número de palavras vezes o tamanho delas.

A complexidade de espaço segue a mesma ideia para a memória extra que o algoritmo usa, sem contar a resposta. O(1) quer dizer que essa memória não muda com o tamanho da entrada.

Dois gráficos. À esquerda, com 10 palavras, as letras comparadas pela força bruta sobem em curva até cerca de 50 mil quando o prefixo comum tem 100 letras, enquanto a solução coluna por coluna fica perto de mil. À direita, com prefixo comum de 60 letras, as letras comparadas pelas soluções 2, 3 e 4 sobem em linha reta com a quantidade de palavras. Com 200 palavras, a menor e maior compara cerca de 24 mil letras, o corte do prefixo cerca de 14 mil e a coluna por coluna cerca de 12 mil

Figura 2. Letras comparadas por cada solução, contadas executando a lógica das soluções sobre listas sorteadas. À esquerda, a força bruta cresce com o quadrado do prefixo. À direita, as outras três crescem em linha reta com a quantidade de palavras. Elaborado para este post.

Solução 1: força bruta

A força bruta testa prefixos cada vez maiores da primeira palavra. Começa com a primeira letra, depois as duas primeiras, e assim por diante. Para cada candidato, confere letra a letra se todas as palavras começam com ele. Quando um candidato falha, o anterior é a resposta.

def prefixo_forca_bruta(strs: list[str]) -> str:
    # Testa prefixos cada vez maiores da primeira palavra
    menor = min(len(p) for p in strs)
    melhor = ""
    for k in range(1, menor + 1):
        candidato = strs[0][:k]
        # Confere letra a letra se todas as palavras começam com o candidato
        if all(p[i] == candidato[i] for p in strs for i in range(k)):
            melhor = candidato
        else:
            break
    return melhor

O laço vai só até o tamanho da menor palavra, porque o prefixo comum não pode ser maior que ela. Em "flower", "flow" e "flight", o candidato "f" passa, o "fl" passa e o "flo" falha em "flight". A resposta fica "fl".

Complexidade de tempo: O(n·p²). Para conferir o candidato de k letras, a função compara k letras em cada uma das n palavras. Como k vai de 1 até p, as primeiras letras são comparadas de novo a cada candidato. Com p = 100 e 10 palavras, foram cerca de 50 mil comparações, como mostra a Figura 2.

Complexidade de espaço: O(m). Cada candidato é uma cópia de até m letras da primeira palavra.

O desperdício está em conferir o começo das palavras várias vezes. As próximas versões olham cada letra uma vez só.

Solução 2: cortar o prefixo

A segunda solução começa supondo que a primeira palavra inteira é o prefixo comum. Depois, passa pelas outras palavras, uma de cada vez. Enquanto a palavra não começa com o prefixo, a última letra do prefixo é cortada. Ao fim da lista, sobra só o que todas dividem.

def prefixo_horizontal(strs: list[str]) -> str:
    # Começa com a primeira palavra inteira como prefixo
    prefixo = strs[0]
    for palavra in strs[1:]:
        # Corta a última letra até a palavra começar com o prefixo
        while not palavra.startswith(prefixo):
            prefixo = prefixo[:-1]
        if not prefixo:
            break  # nada em comum, não adianta continuar
    return prefixo

O método str.startswith diz se um texto começa com outro. Quando o prefixo fica vazio, todo texto começa com ele, e o laço while para sozinho. O break só evita olhar o resto da lista.

Sete linhas mostrando o prefixo a cada passo. No passo 0, o prefixo é flower. Nos passos 1 e 2, flow não começa com ele e as letras r e e são cortadas. No passo 3, flow aceita o prefixo flow. Nos passos 4 e 5, flight não começa com ele e as letras w e o são cortadas. No passo 6, flight aceita o prefixo fl

Figura 3. Corte do prefixo em "flower", "flow" e "flight". O prefixo perde quatro letras e termina em "fl". Elaborado para este post.

Complexidade de tempo: O(n·m + m²). Cada palavra é comparada com o prefixo pelo menos uma vez, com até m letras por comparação. Além disso, o prefixo perde no máximo m letras ao todo, e cada corte custa uma nova comparação de até m letras.

Complexidade de espaço: O(m). Cada corte cria uma cópia nova do prefixo.

A solução pode gastar muito trabalho na primeira palavra quando ela é longa e o prefixo comum é curto. A próxima versão para na primeira diferença, sem cortes.

Solução 3: coluna por coluna

A terceira solução lê as palavras como se estivessem empilhadas, uma embaixo da outra. Ela olha a coluna 0 de todas as palavras, depois a coluna 1, e assim por diante. Na primeira coluna em que uma letra é diferente, ou em que uma palavra acaba, o prefixo termina.

def prefixo_vertical(strs: list[str]) -> str:
    primeira = strs[0]
    # Olha a coluna i de todas as palavras ao mesmo tempo
    for i in range(len(primeira)):
        letra = primeira[i]
        for palavra in strs[1:]:
            # Palavra acabou ou letra diferente: o prefixo termina aqui
            if i == len(palavra) or palavra[i] != letra:
                return primeira[:i]
    return primeira
As palavras flower, flow e flight empilhadas, uma letra por caixa. As colunas 0 e 1, com f e l, estão em verde. Na coluna 2, o o de flower e de flow está em laranja e o i de flight está em vermelho, marcando a primeira diferença. As letras depois da coluna 2 estão em cinza, porque nunca são lidas

Figura 4. Coluna por coluna em "flower", "flow" e "flight". A leitura para na coluna 2, e as letras em cinza nunca são lidas. Elaborado para este post.

Complexidade de tempo: O(n·p), que no pior caso é O(n·m). A função compara cada palavra com a primeira só nas p colunas do prefixo, mais a coluna em que encontra a diferença.

Complexidade de espaço: O(1). Fora a resposta, o código guarda só a posição e a letra da coluna.

Na contagem de letras, esta é a solução que menos compara, como mostra a Figura 2. Mesmo assim, cada comparação passa pelo laço do Python, uma letra por vez. A próxima versão deixa quase todo o trabalho para funções internas do Python.

Solução 4: a menor e a maior palavra

A quarta solução usa a ordem alfabética. Ao colocar as palavras em ordem, a primeira e a última são as que mais diferem no começo. Qualquer letra que as duas dividem no início, as palavras do meio também dividem, porque estão entre elas na ordem. Por isso basta comparar a menor e a maior palavra, que o Python acha com min e max.

def prefixo_min_max(strs: list[str]) -> str:
    # Em ordem alfabética, a menor e a maior palavra são as mais diferentes
    menor, maior = min(strs), max(strs)
    # O que as duas têm em comum, todas têm
    for i, letra in enumerate(menor):
        if letra != maior[i]:
            return menor[:i]
    return menor

O laço percorre a menor palavra e não passa do fim da maior. Se a menor palavra é prefixo da maior, como "a" e "ab", o laço termina sem achar diferença e a resposta é a própria menor palavra.

As palavras fleet, flight, flow, flower e fly em ordem alfabética, uma por linha. Fleet, a menor, e fly, a maior, estão coloridas, com f e l em verde e a terceira letra em vermelho. As três palavras do meio estão em cinza. Abaixo, a frase: menor e maior dividem só fl, então todas dividem só fl

Figura 5. Menor e maior palavra em uma lista de cinco. Só "fleet" e "fly" são comparadas letra a letra no fim, e o prefixo delas vale para a lista toda. Elaborado para este post.

Complexidade de tempo: O(n·m). Para achar a menor e a maior, min e max comparam cada palavra com a menor e a maior já vistas, e cada comparação de textos vai até a primeira letra diferente. Depois, o laço final compara no máximo m letras.

Complexidade de espaço: O(1). Fora a resposta, o código guarda só referências para duas palavras da lista.

Na contagem de letras, esta solução compara cerca do dobro da solução 3, porque min e max passam pela lista cada um uma vez. A diferença está em quem faz o trabalho. As comparações de textos dentro de min e max rodam em C, a linguagem em que o Python é escrito, e não no laço do Python.

Testes

O código das quatro funções deste post é o mesmo do script de testes, executado em Python 3.13.5. O script roda 14 casos fixos em cada solução: os 2 exemplos do enunciado e 12 casos extras, como uma palavra só, palavra vazia, palavras iguais, uma palavra que é prefixo da outra e 200 palavras de 200 letras. Depois, roda 5.000 listas sorteadas com as letras a, b e c, para forçar começos em comum, e compara cada resposta com a função os.path.commonprefix da biblioteca padrão. Ao todo, foram 20.056 verificações (14 × 4 + 5.000 × 4), todas corretas.

Comparação

A Figura 6 mostra o tempo de cada solução pela quantidade de palavras. Para cada quantidade, de 20 a 200, foram sorteadas 10 listas de palavras com 100 letras, todas com um prefixo comum de 60 letras. Cada medida chama a função 100 vezes para cada lista (2 vezes na força bruta, que é muito mais lenta), e cada ponto é o menor tempo de 5 medidas, dividido pelo número de chamadas.

Dois gráficos com o tempo por chamada, em microssegundos, das quatro soluções do Longest Common Prefix para listas de 20 a 200 palavras. À esquerda, em escala logarítmica, a força bruta fica entre 745 e 7.337 microssegundos, a coluna por coluna entre 38 e 331, e o corte do prefixo e a menor e maior ficam abaixo de 7. À direita, em escala linear, o corte do prefixo sobe de 1,8 a 6,0 microssegundos e a menor e maior sobe de 1,4 a 4,2

Figura 6. Tempo por chamada de cada solução do Longest Common Prefix, em microssegundos, para listas de 20 a 200 palavras de 100 letras com prefixo comum de 60. À esquerda, as quatro soluções em escala logarítmica. À direita, só as soluções 2 e 4. Gráfico elaborado para este post com o script de testes, em Python 3.13.5.

Com 200 palavras, a força bruta levou cerca de 7.337 microssegundos (7,3 ms) por chamada. A coluna por coluna levou 331 µs, o corte do prefixo levou 6,0 µs e a menor e maior levou 4,2 µs. A força bruta ficou cerca de 1.700 vezes mais lenta que a solução 4.

O resultado tem uma surpresa. A solução 3 compara menos letras que as soluções 2 e 4, mas foi mais de 50 vezes mais lenta que elas. O motivo é o mesmo dos posts do Palindrome Number e do Roman to Integer. O startswith da solução 2 e o min e o max da solução 4 são funções internas do Python, escritas em C, que comparam letras muito mais rápido que um laço em Python. Já na solução 3 cada letra comparada é uma volta do laço em Python. A solução 4 foi a mais rápida em todas as quantidades.

AbordagemTempoEspaçoObservação
Força brutaO(n·p²)O(m)Confere o começo de novo a cada candidato. Levou 7,3 ms com 200 palavras
Corta o prefixoO(n·m + m²)O(m)Comparações em C com startswith, mas cria uma cópia a cada corte
Coluna por colunaO(n·p)O(1)Compara menos letras, mas uma por vez no laço do Python
Menor e maiorO(n·m)O(1)Compara mais letras, quase todas em C. Mais rápida em todos os tamanhos

A solução 4 é a mais rápida e divide com a solução 3 o menor uso de memória. A solução 3 não depende de funções internas do Python e pode ser escrita do mesmo jeito em qualquer linguagem. Por isso costuma ser a mais fácil de explicar em uma entrevista.

Próximo post da série

O próximo post da série LeetCode Easy, na sexta, 20/11, trata do problema 20, Valid Parentheses. Ele pede para conferir se um texto com parênteses, colchetes e chaves abre e fecha cada um na ordem certa.


Os links da Amazon neste post são de afiliado: se você comprar por eles, recebo uma comissão, sem custo extra para você.

Para saber mais

Leia também