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 dans tous les mots, et ne nécessitent que O(1) mémoire supplémentaire, en plus de la réponse. Le parcours par colonnes est également borné par n × (L+1) , où L est la longueur de la réponse ; il s’arrête donc tôt 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 ?

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

Q: Qu’est-ce qui est préférable : le balayage horizontal ou vertical ?

Les deux ont le même pire cas, O(S) . Le balayage vertical, colonne par colonne, 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 avec de nombreux mots avant qu’un mot situé plus loin ne l’interrompe.

FacileTableaux et chaînes

+10

On vous donne 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 ; ainsi, un mot unique est sa propre réponse.

Fonction

longestCommonPrefix(strs: string-array) → string

strsstring-array: les mots à comparer
Renvoiestring: le plus long préfixe commun à tous les mots, 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 première lettre, donc aucun préfixe n’est commun et 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.

+19 tests cachés à la soumission

Pour aller plus loin

Supposons que la liste reste fixe et que vous receviez de nombreux mots de requête. Comment trouver, pour chaque requête, le préfixe le plus long qu’elle partage avec au moins un mot de la liste, sans parcourir la liste à nouveau à chaque fois ?

Indices

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

0 sur 3 ouverts

Solution

Une lettre appartient à la réponse uniquement si chaque mot contient cette même lettre à la même position, et la réponse s’arrête à la première position où un mot diffère ou n’a plus de lettres. Les deux approches ci-dessous lisent les mots lettre par lettre ; elles diffèrent par l’ordre dans lequel elles les lisent. Le parcours par colonne s’arrête au premier désaccord, il ne lit donc jamais au-delà de la réponse plus une colonne.

Réduisez le préfixe mot par mot

Intuition

Commence par supposer que le premier mot entier est la réponse. Compare-le ensuite au deuxième mot, lettre par lettre, et réduis-le à la partie qu’ils ont en commun. Compare ce qu’il reste au troisième mot, et ainsi de suite. Après le dernier mot, ce qui reste est commun à tous.

C’est correct, car le préfixe commun de nombreux mots est le préfixe commun des deux premiers, puis celui du résultat obtenu et du troisième mot, et ainsi de suite : à chaque étape, il ne peut que rester identique ou raccourcir. Pour interview, internet, interval, internal, 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 d’exécution est O(S), où S est le nombre total de lettres. Tu ne conserves qu’une longueur, pas une copie. Le point faible est l’ordre : avec 200 mots de 200 lettres, dont les 199 premiers sont identiques et dont seul le dernier diffère dès sa première lettre, tu compares les 200 lettres à chacun des 199 premiers mots, soit 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. La colonne 0 contient la première lettre de chaque mot, la colonne 1 la deuxième, et ainsi de suite. Prenez la lettre de strs[0] dans la colonne actuelle et vérifiez que tous les autres mots ont la même lettre à cet endroit. Dès qu’un mot est différent, ou 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 ces colonnes de gauche à droite, puis s’arrête à la première qui interrompt cette suite. Si aucune colonne ne l’interrompt, strs[0] est la réponse ; c’est alors le mot le plus court, ou il est à égalité avec celui-ci.

La boucle lit au plus une colonne au-delà de la réponse. Ainsi, avec n mots et une réponse de longueur L, elle effectue au plus n × (L+1) vérifications, et elle ne lit jamais deux fois la même lettre d’un mot, donc elle est également en O(S). Dans le cas ci-dessus, où 199 mots concordent et où le dernier mot diffère dès sa première lettre, elle s’arrête après la première colonne : 199 comparaisons au lieu de près de 40 000.

Algorithme

Soit first 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

La réponse est courte, et les bugs se cachent à la fin.

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 dans l’ordre donné. Ce raccourci nécessite d’abord de trier les mots : dans abc, xbd, abd, le premier et le dernier partagent ab, mais xbd interrompt la colonne 0 et la réponse est vide.
Renvoyer null ou un espace réservé quand rien 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.
Construire la réponse en ajoutant une lettre à la fois à une chaîne immuable. Pour une réponse de 200 lettres, cela fait 200 copies ; garde une longueur et découpe le premier mot une seule fois à la fin.

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 dans tous les mots, et ne nécessitent que O(1) mémoire supplémentaire, en plus de la réponse. Le parcours par colonnes est également borné par n × (L+1), où L est la longueur de la réponse ; il s’arrête donc tôt 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 situé entre le premier et le dernier commence par ce qu’ils ont en commun ; comparer uniquement le premier et le dernier mot 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 ?

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

Qu’est-ce qui est préférable : le balayage horizontal ou vertical ?

Les deux ont le même pire cas, O(S). Le balayage vertical, colonne par colonne, 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 avec de nombreux mots avant qu’un mot situé plus loin ne l’interrompe.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu

"inter"