Longest Common Prefix

Q: Quelle est la complexité temporelle du plus long préfixe commun ?

Les deux parcours s’exécutent en temps O(S) , où S est le nombre total de lettres, avec une mémoire supplémentaire de O(1) en plus de la réponse. Le parcours par colonnes est également limité par n × (L+1) pour une réponse de longueur L , il s’arrête donc rapidement lorsque les mots diffèrent près du début.

Q: Que doit renvoyer Longest Common Prefix lorsqu’il n’y a aucun préfixe commun ?

La chaîne vide "" . Cela se produit dès que deux mots commencent par des lettres différentes, comme stack , queue et heap .

Q: Quel balayage est préférable : horizontal ou vertical ?

Les deux ont le même pire cas, O(S) . Le balayage vertical est le choix le plus sûr : il s’arrête à la première colonne où un mot diffère, tandis que le balayage horizontal peut comparer un long préfixe à de nombreux mots avant qu’un mot tardif n’y mette fin.

FacileTableaux et chaînes

+10

Vous recevez un tableau de mots strs. Renvoyez la plus longue chaîne par laquelle commence chaque mot. Si les mots ne commencent pas tous par la même lettre, renvoyez la chaîne vide "". Un mot est considéré comme un préfixe de lui-même, donc un mot unique est sa propre réponse.

Fonction

longestCommonPrefix(strs: string-array) → string

strsstring-array: les mots à comparer
Renvoiestring: le préfixe le plus long que tous les mots ont en commun, ou une chaîne vide

Contraintes

1 ≤ strs.length ≤ 200
1 ≤ strs[i].length ≤ 200
Chaque mot ne contient que des lettres minuscules de l’alphabet anglais.

Exemples

Entrée: strs = ["interview", "internet", "interval", "internal"]
Sortie: "inter"
Explication: Les quatre mots commencent par inter. À la position suivante, interview et interval ont un v, tandis que internet et internal ont un n ; le préfixe s’arrête donc là.

Entrée: strs = ["stack", "queue", "heap"]
Sortie: ""
Explication: Les mots commencent par s, q et h. Ils diffèrent dès la toute première lettre, donc la réponse est vide.

Entrée: strs = ["prefix", "pre", "prepare"]
Sortie: "pre"
Explication: pre est le mot le plus court et les deux autres commencent par lui, donc c'est toute la réponse. Un préfixe commun ne peut jamais être plus long que le mot le plus court.

Pour aller plus loin

Supposons que la liste reste fixe et que de nombreux mots-requêtes arrivent. Comment trouveriez-vous le plus long préfixe de chaque requête partagé avec un mot de la liste, sans parcourir à nouveau la liste ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Une lettre ne fait partie de la réponse que si tous les mots la contiennent à la même position, et la réponse s’arrête à la première position où un mot diffère ou s’épuise. Les deux approches lisent les mots lettre par lettre, mais dans un ordre différent. Le parcours par colonne s’arrête au premier désaccord.

Réduisez le préfixe mot par mot

Intuition

Supposons que le premier mot entier soit la réponse. Réduis-le à la partie qu’il partage avec le deuxième mot, puis avec le troisième, et ainsi de suite. Le préfixe commun de plusieurs mots est le préfixe commun des deux premiers, puis de celui-ci et du troisième mot : à chaque étape, on ne peut que le conserver ou le raccourcir. Par exemple 1, le candidat passe de interview à inter après le deuxième mot et reste ainsi.

Chaque lettre est comparée au plus une fois, donc le temps est de O(S) pour S lettres au total. Le point faible est l’ordre : avec 200 mots de 200 lettres où seul le dernier mot diffère dès sa première lettre, tu effectues près de 40 000 comparaisons avant que le dernier mot ne réduise le préfixe à rien.

Algorithme

Définissez prefixLen sur la longueur de strs[0].
Pour chaque autre mot, comptez le nombre de lettres initiales qu’il partage avec strs[0], jusqu’à prefixLen.
Définissez prefixLen sur ce nombre et arrêtez-vous plus tôt s’il atteint 0.
Retournez les prefixLen premières lettres 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]

Comparez colonne par colonne

Intuition

Lisez les mots comme un tableau, une colonne à la fois. Prenez la lettre de strs[0] dans la colonne en cours et vérifiez que tous les autres mots ont la même lettre à cet endroit. Dès qu’un mot diffère, ou est trop court pour avoir cette colonne, la réponse est strs[0] jusqu’à cette colonne.

La réponse correspond exactement à la suite de colonnes où tous les mots concordent, et cette boucle parcourt cette suite de gauche à droite et s’arrête là où elle s’interrompt. Si rien ne l’interrompt, strs[0] est la réponse.

Avec n mots et une réponse de longueur L, la boucle effectue au maximum n × (L+1) vérifications, ce qui correspond également à O(S). Si seul le dernier de 200 mots diffère à sa première lettre, elle s’arrête après 199 comparaisons.

Algorithme

Soit first égal à strs[0].
Pour chaque colonne col, de 0 à la longueur de first moins un, lisez first[col].
Pour chaque autre mot, s’il n’a pas de lettre à la position col ou si sa lettre est différente, renvoyez les col premières lettres de first.
Si toutes les colonnes correspondent, renvoyez 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

Pièges et cas limites

Lire au-delà de la fin d’un mot plus court. Dans prefix, pre, prepare, la colonne 3 existe dans prefix, mais pas dans pre ; vérifie la longueur avant de lire la lettre.
Comparer uniquement le premier et le dernier mot sans les trier. Dans abc, xbd, abd, ces deux mots partagent ab, mais xbd ne correspond pas à la colonne 0 et la réponse est vide.
Renvoyer null ou un espace réservé lorsqu’aucun préfixe n’est commun. La réponse est la chaîne vide.
Oublier qu’un mot unique est son propre préfixe : algorithm seul renvoie algorithm.
Ajouter une lettre à la fois à une chaîne immuable. Une réponse de 200 lettres entraîne alors 200 copies ; conserve une longueur et découpe une seule fois le premier mot.

Questions fréquentes4

Quelle est la complexité temporelle du plus long préfixe commun ?

Les deux parcours s’exécutent en temps O(S), où S est le nombre total de lettres, avec une mémoire supplémentaire de O(1) en plus de la réponse. Le parcours par colonnes est également limité par n × (L+1) pour une réponse de longueur L, il s’arrête donc rapidement lorsque les mots diffèrent près du début.

Peux-tu trouver le plus long préfixe commun en triant les mots ?

Oui. Par ordre alphabétique, chaque mot entre le premier et le dernier commence par ce que ces deux mots ont en commun ; comparer uniquement ces deux mots donne donc la réponse. Le tri compare environ n log n paires de mots, ce qui coûte plus cher qu’un seul parcours, mais le code est court.

Que doit renvoyer Longest Common Prefix lorsqu’il n’y a aucun préfixe commun ?

La chaîne vide "". Cela se produit dès que deux mots commencent par des lettres différentes, comme stack, queue et heap.

Quel balayage est préférable : horizontal ou vertical ?

Les deux ont le même pire cas, O(S). Le balayage vertical est le choix le plus sûr : il s’arrête à la première colonne où un mot diffère, tandis que le balayage horizontal peut comparer un long préfixe à de nombreux mots avant qu’un mot tardif n’y mette fin.

def longestCommonPrefix(strs):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

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

Résultat attendu

"inter"