Nombre de façons de former une chaîne cible à partir d'un dictionnaire-tutoriel php-php.cn

Nombre de façons de former une chaîne cible à partir d'un dictionnaire

Mary-Kate Olsen

Libérer： 2024-12-30 17:34:15

original

210 Les gens l'ont consulté

Number of Ways to Form a Target String Given a Dictionary

1639. Nombre de façons de former une chaîne cible à partir d'un dictionnaire

Difficulté : Difficile

Sujets :Array, String, Programmation dynamique

Vous recevez une liste de chaînes de même longueur mots et une cible de chaîne.

Votre tâche consiste à former une cible en utilisant les mots donnés selon les règles suivantes :

la cible doit être formée de gauche à droite.
Pour former le i^ème caractère (0-indexé) de la cible, vous pouvez choisir le k^ème caractère du j^ème chaîne de mots si target[i] = mots[j][k].
Une fois que vous utilisez le k^ème caractère de la j^ème chaîne de mots, vous ne pouvez plus utiliser le x^ème caractère de n'importe quelle chaîne en mots où x <= k. En d'autres termes, tous les caractères à gauche ou à l'index k deviennent inutilisables pour chaque chaîne.
Répétez le processus jusqu'à ce que vous formiez la chaîne cible.

Avis que vous pouvez utiliser plusieurs caractères de la même chaîne dans les mots à condition que les conditions ci-dessus soient remplies.

Renvoyer le nombre de façons de former une cible à partir de mots. Puisque la réponse est peut-être trop grande, renvoyez-la modulo 10⁹7.

Exemple 1 :

Entrée : mots = ["acca","bbbb","caca"], cible = "aba"
Sortie : 6
Explication : Il existe 6 façons de former une cible.
- "aba" -> indice 0 ("acca"), indice 1 ("bbbb"), indice 3 ("caca")
- "aba" -> indice 0 ("acca"), indice 2 ("bbbb"), indice 3 ("caca")
- "aba" -> indice 0 ("acca"), indice 1 ("bbbb"), indice 3 ("acca")
- "aba" -> indice 0 ("acca"), indice 2 ("bbbb"), indice 3 ("acca")
- "aba" -> indice 1 ("caca"), indice 2 ("bbbb"), indice 3 ("acca")
- "aba" -> indice 1 ("caca"), indice 2 ("bbbb"), indice 3 ("caca")
Exemple 2 :
- Entrée : mots = ["abba","baab"], cible = "bab"
- Sortie : 4
- Explication : Il existe 4 façons de former une cible.
  - "bab" -> indice 0 ("baab"), indice 1 ("baab"), indice 2 ("abba")
  - "bab" -> indice 0 ("baab"), indice 1 ("baab"), indice 3 ("baab")
  - "bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab")
  - "bab" -> indice 1 ("abba"), indice 2 ("baab"), indice 3 ("baab")
Contraintes :
- 1 <= mots.longueur <= 1000
- 1 <= mots[i].length <= 1000
- Toutes les chaînes des mots ont la même longueur.
- 1 <= target.length <= 1000
- les mots [i] et la cible ne contiennent que des lettres anglaises minuscules.
Indice :
1. Pour chaque index i, stockez la fréquence de chaque caractère dans la i^ème ligne.
2. Utilisez la programmation dynamique pour calculer le nombre de façons d'obtenir la chaîne cible à l'aide du tableau de fréquences.
Solution :

Le problème nécessite de trouver le nombre de façons de former une chaîne cible à partir d'un dictionnaire de mots, en suivant des règles spécifiques concernant l'utilisation des caractères. Il s'agit d'un problème combinatoire qui peut être résolu efficacement en utilisant la Programmation dynamique (DP) et le prétraitement des fréquences de caractères.

Points clés
1. Contraintes :
  - Les mots sont de même longueur.
  - Les caractères des mots ne peuvent être utilisés que de gauche à droite.
2. Défis :
  - Compter efficacement les façons de former une cible en raison de contraintes importantes.
  - Évitez le recalcul avec mémoïsation.
3. Module :
  - Le résultat pouvant être important, tous les calculs sont effectués modulo 10⁹7.
Approche

La solution utilise :
1. Prétraitement :
  - Comptez la fréquence de chaque caractère à chaque position dans tous les mots.
2. Programmation dynamique :
  - Utilisez un tableau DP 2D pour calculer le nombre de façons de former la chaîne cible.
Étapes :
1. Prétraitez les mots dans un tableau de fréquences (comptes).
2. Définissez une fonction DP pour trouver de manière récursive le nombre de façons de former une cible à l'aide des décomptes prétraités.
Planifier
1. Analyse des entrées :
  - Acceptez les mots et ciblez.
2. Prétraitement :
  - Créez un tableau counts où counts[j][char] représente la fréquence du caractère à la position j dans tous les mots.
3. Programmation dynamique :
  - Utilisez une fonction récursive avec mémorisation pour calculer le nombre de façons de former une cible en utilisant des caractères provenant de positions valides dans les mots.
4. Renvoyer le résultat :
  - Renvoyer le nombre total modulo 10⁹7.
Implémentons cette solution en PHP : 1639. Nombre de façons de former une chaîne cible à partir d'un dictionnaire
```
  
  
  Explication:




Étape de prétraitement :

Créez un tableau de comptes :


Pour chaque colonne en mots, comptez les occurrences de chaque caractère.


Exemple : Si mots = ["acca", "bbbb", "caca"], pour la première colonne, compte[0] = {'a' : 1, 'b' : 1, 'c' : 1 }.



DP récursif :


Définir dp(i, j) :



i est l'index actuel dans la cible.

j est la position actuelle dans les mots.


Cas de base :


Si i == len(target) : Cible entière formée → renvoyer 1.
Si j == len(words[0]) : Plus de colonnes à utiliser → renvoie 0.


Récidive :


Option 1 : utilisez les caractères count[j][target[i]] à partir de la position j.
Option 2 : Sauter la position j.





Optimisation :


Utilisez une table de mémorisation pour stocker les résultats des sous-problèmes qui se chevauchent.





  
  
  Exemple de procédure pas à pas


Entrée :


mots = ["acca", "bbbb", "caca"], cible = "aba"



Prétraitement :


comptes[0] = {'a' : 2, 'b' : 0, 'c' : 1}
comptes[1] = {'a' : 0, 'b' : 3, 'c' : 0}
comptes[2] = {'a' : 1, 'b' : 0, 'c' : 2}
comptes[3] = {'a' : 2, 'b' : 0, 'c' : 1}



Calcul DP :



dp(0, 0) : Combien de façons de former "aba" à partir de la colonne 0.
Calculer de manière récursive, en combinant l'utilisation de comptes et le saut de colonnes.




Sortie : 6


  
  
  Complexité temporelle




Prétraitement : O(n x m), où n est le nombre de mots et m est leur longueur.

Programmation dynamique : O(l x m), où l est la longueur de la cible.

Total : O(n x m l x m).



  
  
  Sortie pour exemple




Entrée :
mots = ["acca", "bbbb", "caca"], cible = "aba"


Sortie : 6



Ce problème est un excellent exemple de combinaison de prétraitement et de programmation dynamique pour résoudre efficacement un défi combinatoire.

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



          

            
  

            
        
```