Trouver la longueur du préfixe commun le plus long

3043. Trouver la longueur du préfixe commun le plus long

Difficulté :Moyen

Sujets : Tableau, table de hachage, chaîne, trie

Vous recevez deux tableaux avec des entiers positifs arr1 et arr2.

Un préfixe d'un entier positif est un entier formé par un ou plusieurs de ses chiffres, en commençant par son chiffre le plus à gauche. Par exemple, 123 est un préfixe de l'entier 12345, tandis que 234 ne l'est pas.

Un préfixe commun de deux entiers a et b est un entier c, tel que c est un préfixe à la fois de a et de b. Par exemple, 5655359 et 56554 ont un préfixe commun 565 tandis que 1223 et 43456 n'ont pas ont un préfixe commun.

Vous devez trouver la longueur du préfixe commun le plus long entre toutes les paires d'entiers (x, y) tels que x appartient à arr1 et y appartient à arr2.

Renvoie la longueur du préfixe commun le plus long parmi toutes les paires. Si aucun préfixe commun n'existe entre eux, renvoyez 0.

Exemple 1 :

• Entrée : arr1 = [1,10,100], arr2 = [1000]
• Sortie : 3
• Explication : Il y a 3 paires (arr1[i], arr2[j]) :
  • Le préfixe commun le plus long de (1, 1000) est 1.
  • Le préfixe commun le plus long de (10, 1000) est 10.
  • Le préfixe commun le plus long de (100, 1000) est 100.
  • Le préfixe commun le plus long est 100 avec une longueur de 3.

Exemple 2 :

• Entrée : arr1 = [1,2,3], arr2 = [4,4,4]
• Sortie : 4
• Explication : Il n'existe aucun préfixe commun pour aucune paire (arr1[i], arr2[j]), nous renvoyons donc 0.
  • Notez que les préfixes communs entre les éléments d'un même tableau ne comptent pas.

Contraintes :

• 1 <= arr1.length, arr2.length <= 5 * 10⁴
• 1 <= arr1[i], arr2[i] <= 10⁸

Indice :

1. Mettez tous les préfixes possibles de chaque élément de arr1 dans un HashSet.
2. Pour tous les préfixes possibles de chaque élément dans arr2, vérifiez s'il existe dans le HashSet.

Solution :

Nous pouvons utiliser un HashSet pour stocker les préfixes d'un tableau, puis vérifier ces préfixes dans le deuxième tableau.

Approche:

1. Générer des préfixes : Pour chaque numéro de arr1 et arr2, générez tous les préfixes possibles. Un préfixe est formé d'un ou plusieurs chiffres commençant par le chiffre le plus à gauche.

2. Stocker les préfixes de arr1 dans un ensemble : L'utilisation d'un HashSet pour stocker tous les préfixes de nombres dans arr1 garantit des recherches rapides lors de la vérification des préfixes de arr2.

3. Trouver le préfixe commun le plus long : Pour chaque numéro de l'arr2, générez ses préfixes et vérifiez si l'un de ces préfixes existe dans le HashSet à partir de l'étape 2. Suivez le préfixe le plus long trouvé.

4. Renvoyer la longueur du préfixe commun le plus long : Si un préfixe commun est trouvé, renvoie sa longueur ; sinon, renvoie 0.

Implémentons cette solution en PHP : 3043. Trouver la longueur du préfixe commun le plus long

  
  
  Explication:




Création de HashSet :


Nous créons d'abord un tableau associatif $prefixSet pour contenir tous les préfixes possibles des nombres dans arr1.
Nous parcourons chaque nombre de arr1, le convertissons en chaîne et extrayons tous ses préfixes à l'aide de la fonction substr. Chaque préfixe est stocké dans le $prefixSet.



Vérification des préfixes :


Ensuite, nous parcourons chaque nombre de arr2, en le convertissant également en chaîne.
Pour chaque numéro de arr2, nous extrayons à nouveau tous les préfixes possibles.
Si un préfixe existe dans $prefixSet, nous vérifions si sa longueur est supérieure à la longueur maximale actuelle trouvée ($maxLength).



Renvoyer le résultat :


Enfin, nous renvoyons la longueur du préfixe commun le plus long trouvé.





  
  
  Complexité:




Complexité temporelle : O(n * m) où n et m sont respectivement les longueurs de arr1 et arr2. En effet, nous traitons chaque numéro et leurs préfixes.

Complexité spatiale : O(p) où p est le nombre total de préfixes stockés dans le HashSet.


Cette solution est efficace et fonctionne bien dans les contraintes fournies.

Liens de contact
Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!