Longest Common Prefix

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

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

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

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 é a opção mais segura: ela para na primeira coluna em que qualquer palavra diverge, enquanto a varredura horizontal pode comparar um prefixo longo com muitas palavras antes que uma palavra posterior o interrompa.

FácilArrays e strings

+10

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

Função

longestCommonPrefix(strs: string-array) → string

strsstring-array: as palavras a 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
Toda 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 próxima posição, interview e interval têm um v, e internet e internal têm um n, então 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 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 comum nunca pode ser mais longo do que a palavra mais curta.

Para ir além

Suponha que a lista permaneça fixa e que muitas palavras de consulta cheguem. Como você encontraria o prefixo mais longo de cada consulta compartilhado com alguma palavra da lista, sem percorrer a lista novamente?

Dicas

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

0 de 3 abertas

Solução

Uma letra pertence à resposta somente se todas as palavras a tiverem na mesma posição, e a resposta termina na primeira posição em que uma palavra diverge ou acaba. As duas abordagens leem as palavras letra por letra, em uma ordem diferente. A varredura por coluna para na primeira divergência.

Encurte o prefixo palavra por palavra

Intuição

Suponha que a primeira palavra inteira seja a resposta. Reduza-a à parte que ela tem em comum com a segunda palavra, depois com a terceira e assim por diante. O prefixo comum de muitas palavras é o prefixo comum das duas primeiras, depois desse prefixo com a terceira palavra: cada etapa só pode mantê-lo ou encurtá-lo. Por exemplo, no exemplo 1, o candidato passa de interview para inter após a segunda palavra e permanece assim.

Cada letra é comparada no máximo uma vez, então o tempo é O(S) para S letras ao todo. O ponto fraco é a ordem: com 200 palavras de 200 letras, em que apenas a última palavra difere na primeira letra, você faz quase 40.000 comparações antes que a última palavra reduza o prefixo a nada.

Algoritmo

Defina prefixLen como o comprimento de strs[0].
Para cada outra palavra, 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. Pegue a letra de strs[0] na coluna atual e confira se todas as outras palavras têm a mesma letra nessa posição. Na primeira vez que uma palavra divergir ou for curta demais para ter aquela coluna, a resposta será strs[0] até essa coluna.

A resposta é exatamente a sequência de colunas em que todas as palavras concordam, e este loop percorre essa sequência da esquerda para a direita e para onde ela se interrompe. Se nada a interromper, strs[0] será a resposta.

Com n palavras e uma resposta de comprimento L, o loop faz no máximo n × (L+1) verificações, o que também é O(S). No caso em que apenas a última de 200 palavras difere na primeira letra, ele para após 199 comparações.

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

Ler além do fim 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 sem ordenar. Em abc, xbd, abd, essas duas compartilham ab, mas xbd quebra a coluna 0 e a resposta é vazia.
Retornar null ou um marcador quando nada é compartilhado. A resposta é a string vazia.
Esquecer que uma única palavra é seu próprio prefixo: algorithm sozinho retorna algorithm.
Adicionar uma letra por vez a uma string imutável. Uma resposta de 200 letras custaria então 200 cópias; mantenha um comprimento e corte a primeira palavra uma vez.

Perguntas frequentes4

Qual é a complexidade de tempo do maior prefixo comum?

As duas varreduras são executadas em tempo O(S), em que S é o número total de letras, com memória extra O(1) além da resposta. A varredura por coluna também é limitada por n × (L+1) para uma resposta de comprimento L, então ela para mais cedo quando as palavras discordam 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 essas duas dá a resposta. A ordenação compara cerca de n log n pares de palavras, o que custa mais do que uma única varredura, mas o código é curto.

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

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 é a opção mais segura: ela para na primeira coluna em que qualquer palavra diverge, enquanto a varredura horizontal pode comparar um prefixo longo com muitas palavras antes que uma palavra posterior o interrompa.

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

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada

"inter"