Caractères supplémentaires dans une chaîne

2707. Caractères supplémentaires dans une chaîne

Difficulté :Moyen

Sujets : Tableau, table de hachage, chaîne, programmation dynamique, Trie

Vous recevez une chaîne indexée à 0 et un dictionnaire de mots. Vous devez diviser s en une ou plusieurs sous-chaînes ne se chevauchant de telle sorte que chaque sous-chaîne soit présente dans le dictionnaire. Il peut y avoir des caractères supplémentaires dans les s qui ne sont présents dans aucune des sous-chaînes.

Renvoyer le nombre minimum de caractères supplémentaires restants si vous divisez les s de manière optimale.

Exemple 1 :

• Entrée : s = "leetscode", dictionnaire = ["leet","code","leetcode"]
• Sortie : 1
• Explication : On peut diviser s en deux sous-chaînes : "leet" de l'index 0 à 3 et "code" de l'index 5 à 8. Il n'y a qu'un seul caractère inutilisé (à l'index 4), donc on renvoie 1 .

Exemple 2 :

• Entrée : s = "sayhelloworld", dictionnaire = ["hello","world"]
• Sortie : 3
• Explication : On peut diviser s en deux sous-chaînes : "hello" de l'index 3 à 7 et "world" de l'index 8 à 12. Les caractères aux indices 0, 1, 2 ne sont utilisés dans aucune sous-chaîne et sont donc considérés comme des caractères supplémentaires. Par conséquent, nous retournons 3.

Contraintes :

• 1 <= s.length <= 50
• 1 <= dictionnaire.longueur <= 50
• 1 <= dictionnaire[i].length <= 50
• le dictionnaire [i] et s se compose uniquement de lettres anglaises minuscules
• le dictionnaire contient des mots distincts

Indice :

1. Pouvons-nous utiliser la programmation dynamique ici ?
2. Définissez DP[i] comme caractère supplémentaire minimum si vous divisez s[0:i] de manière optimale.

Solution :

Nous pouvons définir un tableau dp où dp[i] représente le nombre minimum de caractères supplémentaires dans la sous-chaîne s[0:i] après une segmentation optimale.

Approche:

1. Définition de la programmation dynamique :

   • Soit dp[i] le nombre minimum de caractères supplémentaires dans la sous-chaîne s[0:i].
   • Pour calculer dp[i], on peut :
     • Soit considérer le caractère s[i-1] comme un caractère supplémentaire et passer à l'index suivant.
     • Ou vérifiez si une sous-chaîne se terminant par l'index i existe dans le dictionnaire, et si c'est le cas, utilisez-la pour réduire les caractères supplémentaires.

2. Transition :

   • Pour chaque indice i, on soit :
     • Ajoutez-en un à dp[i-1] si nous traitons s[i] comme un caractère supplémentaire.
     • Vérifiez toutes les sous-chaînes possibles s[j:i] (pour j < i) et si s[j:i] est dans le dictionnaire, nous mettons à jour dp[i] en fonction de dp[j].

3. Résultat :

   • La valeur de dp[len(s)] nous donnera le nombre minimum de caractères supplémentaires dans la chaîne entière s.

Implémentons cette solution en PHP : 2707. Caractères supplémentaires dans une chaîne

  
  
  Explication:




Cas de base :



dp[0] = 0 puisqu'aucun caractère supplémentaire n'existe dans une chaîne vide.



Recherche dans le dictionnaire :


Nous stockons les mots du dictionnaire dans une carte de hachage en utilisant array_flip() pour une recherche à temps constant.



Transition :


Pour chaque position i, nous vérifions toutes les sous-chaînes possibles s[j:i]. Si une sous-chaîne existe dans le dictionnaire, nous mettons à jour la valeur dp[i].



Complexité temporelle :


La complexité temporelle est O(n^2) où n est la longueur de la chaîne s car pour chaque index, nous vérifions tous les indices précédents pour former des sous-chaînes.





  
  
  Résultats des tests :


Pour l'entrée "leetscode" avec le dictionnaire ["leet","code","leetcode"], la fonction renvoie correctement 1, car il ne reste qu'un seul caractère supplémentaire ("s").

Pour l'entrée "sayhelloworld" avec le dictionnaire ["hello","world"], la fonction renvoie 3, car les trois premiers caractères ("say") sont supplémentaires.

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!