Longest Common Prefix

Q: Qual é a complexidade de tempo do prefixo comum mais longo?

Ambas as varreduras são executadas em tempo O(S) , em que S é o número total de letras em todas as palavras, e precisam de apenas O(1) de memória extra além da resposta. A varredura por colunas também é limitada por n × (L+1) , em que L é o comprimento da resposta, então ela para mais cedo quando as palavras divergem perto do início.

Q: O que Longest Common Prefix deve retornar quando não há um prefixo comum?

Ele retorna a string vazia "" . Isso acontece assim que duas palavras começam com letras diferentes, como em stack , queue e heap .

Q: Qual é melhor, a varredura horizontal ou vertical?

Ambos têm o mesmo pior caso, O(S) . A varredura vertical, coluna por coluna, é a opção mais segura: ela para na primeira coluna em que alguma palavra diverge, enquanto a varredura horizontal pode comparar um prefixo longo com muitas palavras antes que uma palavra mais adiante o interrompa.

FácilArrays e strings

+10

Você recebe um array de palavras strs. Retorne a string mais longa com a qual todas as palavras começam. Se as palavras não começarem todas com a mesma letra, retorne a string vazia "". Uma palavra conta como prefixo de si mesma, então uma única palavra é a própria resposta.

Função

longestCommonPrefix(strs: string-array) → string

strsstring-array: as palavras para comparar
Retornastring: o prefixo mais longo compartilhado por todas as palavras, ou uma string vazia

Restrições

1 ≤ strs.length ≤ 200
1 ≤ strs[i].length ≤ 200
Cada palavra contém apenas letras minúsculas do alfabeto inglês.

Exemplos

Entrada: strs = ["interview", "internet", "interval", "internal"]
Saída: "inter"
Explicação: As quatro palavras começam com inter. Na posição seguinte, interview e interval têm um v, enquanto internet e internal têm um n; por isso, o prefixo termina ali.

Entrada: strs = ["stack", "queue", "heap"]
Saída: ""
Explicação: As palavras começam com s, q e h. Elas diferem já na primeira letra, então não compartilham nenhum prefixo e a resposta é vazia.

Entrada: strs = ["prefix", "pre", "prepare"]
Saída: "pre"
Explicação: pre é a palavra mais curta, e as outras duas começam com ela, então ela é a resposta completa. Um prefixo compartilhado nunca pode ser mais longo do que a palavra mais curta.

+19 testes ocultos ao enviar

Para ir além

Suponha que a lista permaneça fixa e você receba muitas palavras de consulta. Como encontraria, para cada consulta, o prefixo mais longo que ela compartilha com pelo menos uma palavra da lista, sem percorrer a lista novamente a cada vez?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Uma letra faz parte da resposta somente se todas as palavras tiverem essa mesma letra na mesma posição, e a resposta termina na primeira posição em que alguma palavra diverge ou acaba. As duas abordagens abaixo leem as palavras letra por letra; elas diferem na ordem em que fazem essa leitura. A varredura por coluna para na primeira divergência, então nunca lê além da resposta mais uma coluna.

Encurte o prefixo palavra por palavra

Intuição

Comece supondo que a primeira palavra inteira é a resposta. Em seguida, compare-a com a segunda palavra letra por letra e reduza-a à parte que elas têm em comum. Compare o que restou com a terceira palavra, e assim por diante. Depois da última palavra, o que restar será comum a todas elas.

Isso está correto porque o prefixo comum de muitas palavras é o prefixo comum das duas primeiras, depois o prefixo comum desse resultado e da terceira palavra, e assim por diante: cada etapa só pode mantê-lo ou encurtá-lo. Para interview, internet, interval, internal, o candidato passa de interview para inter depois da segunda palavra e permanece assim.

Cada letra é comparada no máximo uma vez, então o tempo é O(S), em que S é o número total de letras. Você mantém apenas um comprimento, não uma cópia. O ponto fraco é a ordem: com 200 palavras de 200 letras, em que as primeiras 199 concordam e apenas a última difere na primeira letra, você compara todas as 200 letras com cada uma das primeiras 199 palavras, chegando perto de 40.000 comparações, antes de a última palavra reduzir o prefixo a nada.

Algoritmo

Defina prefixLen como o comprimento de strs[0].
Para cada uma das outras palavras, conte quantas letras iniciais ela compartilha com strs[0], até prefixLen.
Defina prefixLen como essa quantidade e pare antes se ela chegar a 0.
Retorne as primeiras prefixLen letras de strs[0].

def longestCommonPrefix(strs):
    first = strs[0]
    prefix_len = len(first)
    for word in strs[1:]:
        common = 0
        while common < prefix_len and common < len(word) and word[common] == first[common]:
            common += 1
        prefix_len = common
        if prefix_len == 0:
            break
    return first[:prefix_len]

Compare coluna por coluna

Intuição

Leia as palavras como uma tabela, uma coluna de cada vez. A coluna 0 contém a primeira letra de cada palavra, a coluna 1 contém a segunda, e assim por diante. Pegue a letra de strs[0] na coluna atual e verifique se todas as outras palavras têm a mesma letra nessa posição. Na primeira vez que uma palavra tiver uma letra diferente, ou for curta demais para ter essa coluna, a resposta será strs[0] até essa coluna.

A resposta é exatamente a sequência de colunas em que todas as palavras coincidem, e esse loop percorre essas colunas da esquerda para a direita, parando na primeira que interrompe a sequência. Se nenhuma coluna a interromper, strs[0] será a própria resposta; nesse caso, ela é a palavra mais curta ou tem o mesmo comprimento que ela.

O loop lê no máximo uma coluna além da resposta; portanto, com n palavras e uma resposta de comprimento L, ele realiza no máximo n × (L+1) verificações e nunca lê a mesma letra de uma palavra duas vezes, então também é O(S). No caso acima, em que 199 palavras coincidem e a última palavra difere já na primeira letra, ele para após a primeira coluna: 199 comparações, em vez de quase 40.000.

Algoritmo

Seja first igual a strs[0].
Para cada coluna col, de 0 até o comprimento de first menos um, leia first[col].
Para cada outra palavra, se ela não tiver uma letra na posição col ou se a letra for diferente, retorne as primeiras col letras de first.
Se todas as colunas corresponderem, retorne first.

def longestCommonPrefix(strs):
    first = strs[0]
    for col in range(len(first)):
        for word in strs[1:]:
            if col == len(word) or word[col] != first[col]:
                return first[:col]
    return first

Armadilhas e casos extremos

A resposta é curta e os bugs estão no final.

Ler além do final de uma palavra mais curta. Em prefix, pre, prepare, a coluna 3 existe em prefix, mas não em pre; verifique o comprimento antes de ler a letra.
Comparar apenas a primeira e a última palavra na ordem fornecida. Esse atalho exige que as palavras sejam ordenadas primeiro: em abc, xbd, abd, a primeira e a última compartilham ab, mas xbd interrompe a coluna 0 e a resposta é vazia.
Retornar null ou um valor provisório quando nada é compartilhado. A resposta é a string vazia.
Esquecer que uma única palavra é o próprio prefixo: algorithm sozinho retorna algorithm.
Construir a resposta adicionando uma letra de cada vez a uma string imutável. Para uma resposta de 200 letras, isso são 200 cópias; mantenha um comprimento e extraia o início da primeira palavra apenas uma vez, no final.

Perguntas frequentes4

Qual é a complexidade de tempo do prefixo comum mais longo?

Ambas as varreduras são executadas em tempo O(S), em que S é o número total de letras em todas as palavras, e precisam de apenas O(1) de memória extra além da resposta. A varredura por colunas também é limitada por n × (L+1), em que L é o comprimento da resposta, então ela para mais cedo quando as palavras divergem perto do início.

Você consegue encontrar o prefixo comum mais longo ordenando as palavras?

Sim. Em ordem alfabética, todas as palavras entre a primeira e a última começam com o que essas duas têm em comum, então comparar apenas a primeira e a última palavra dá a resposta. A ordenação compara cerca de n log n pares de palavras, o que custa mais do que uma varredura, mas o código é curto.

O que Longest Common Prefix deve retornar quando não há um prefixo comum?

Ele retorna a string vazia "". Isso acontece assim que duas palavras começam com letras diferentes, como em stack, queue e heap.

Qual é melhor, a varredura horizontal ou vertical?

Ambos têm o mesmo pior caso, O(S). A varredura vertical, coluna por coluna, é a opção mais segura: ela para na primeira coluna em que alguma palavra diverge, enquanto a varredura horizontal pode comparar um prefixo longo com muitas palavras antes que uma palavra mais adiante o interrompa.

Python

def longestCommonPrefix(strs):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

strs = ["interview", "internet", "interval", "internal"]

Esperado

"inter"