Maior prefixo comum
A missão
Problema
Dada uma coleção de palavras, encontre a maior sequência inicial de caracteres com que todas as palavras começam. A sequência precisa começar no primeiro caractere de cada palavra, então uma coincidência que aparece mais adiante em uma palavra não conta. Retorne a string vazia quando as palavras não compartilham nem o primeiro caractere.
Exemplos
Input: words = ["flower", "flow", "flight"]
Output: "fl"
Por quê: a terceira palavra quebra a concordância no terceiro caractere
Input: words = ["dog", "racecar"]
Output: ""
Por quê: as palavras divergem logo de cara
Input: words = []
Output: ""
Por quê: edge case: não há palavras para comparar
Dicas
0 / 3
Comparar as palavras entre si, aos pares, dá mais trabalho do que o necessário. A resposta nunca pode ser mais longa que qualquer uma das palavras, então uma única palavra pode servir de régua.
Alinhe as palavras uma embaixo da outra e pense em colunas, não em palavras. A resposta termina na primeira coluna em que elas deixam de concordar.
Percorra os caracteres da primeira palavra por posição. Em cada posição, verifique se todas as outras palavras são longas o bastante e têm o mesmo caractere ali. A primeira falha termina o prefixo nessa posição, e sobreviver a todas as posições significa que a primeira palavra inteira é o prefixo.
- Tempo-alvo
- O(total characters)
- Espaço-alvo
- O(len(words) + len(words[0]))
Solução
A resposta nunca pode passar do tamanho da primeira palavra, então essa palavra serve de régua e a busca acontece sobre as posições dela. Varrer coluna por coluna para na primeira posição em que alguma palavra é curta demais ou diverge, que é exatamente onde o prefixo comum termina. Comparar todas as palavras em cada coluna, em vez de palavra contra palavra, faz a varredura parar o mais cedo possível. O tempo é O(total de caracteres) no pior caso, e o espaço é O(1) além da fatia retornada.
def longest_shared_prefix(words):
if not words:
return ""
for i, ch in enumerate(words[0]): # walk the yardstick word column by column
for word in words[1:]:
if i >= len(word) or word[i] != ch:
return words[0][:i] # this column breaks the agreement
return words[0] # every column survived the check
print(longest_shared_prefix(["flower", "flow", "flight"])) # -> fl
print(longest_shared_prefix(["dog", "racecar"])) # ->
print(longest_shared_prefix([])) # ->Travou na ideia, e não no código? O básico de strings explica isso.