Similarité des phrases III

1813. Similitude des phrases III

Difficulté :Moyen

Sujets : Tableau, deux pointeurs, chaîne

Vous recevez deux chaînes phrase1 et phrase2, chacune représentant une phrase composée de mots. Une phrase est une liste de mots séparés par un simple espace sans espaces de début ou de fin. Chaque mot est composé uniquement de caractères anglais majuscules et minuscules.

Deux phrases s1 et s2 sont considérées comme similaires s'il est possible d'insérer une phrase arbitraire (éventuellement vide) à l'intérieur d'une de ces phrases telle que les deux phrases deviennent égales. Notez que la phrase insérée doit être séparée des mots existants par des espaces.

Par exemple,

• s1 = "Bonjour Jane" et s2 = "Bonjour, je m'appelle Jane" peuvent être rendus égaux en insérant "je m'appelle" entre "Bonjour" et "Jane" dans s1.
• s1 = "Frog cool" et s2 = "Frogs are cool" ne sont pas similaires, car bien qu'il y ait une phrase "s are" insérée dans s1, elle n'est pas séparée de "Frog" par un espace.

Étant donné deux phrases phrase1 et phrase2, renvoie true si phrase1 et phrase2 sont similaires. Sinon, retournez false.

Exemple 1 :

• Entrée : phrase1 = "Je m'appelle Haley", phrase2 = "Ma Haley"
• Sortie : vrai
• Explication : la phrase2 peut être transformée en phrase1 en insérant « le nom est » entre « Mon » et « Haley ».

Exemple 2 :

• Entrée : phrase1 = "de", phrase2 = "Beaucoup de mots"
• Sortie : faux
• Explication : Aucune phrase ne peut être insérée à l'intérieur d'une des phrases pour la rendre égale à l'autre.

Exemple 3 :

• Entrée : phrase1 = "Manger maintenant", phrase2 = "Manger"
• Sortie : vrai
• Explication : la phrase2 peut être transformée en phrase1 en insérant « maintenant » à la fin de la phrase.

Contraintes :

• 1 <= phrase1.length, phrase2.length <= 100
• la phrase1 et la phrase2 sont constituées de lettres et d'espaces anglais minuscules et majuscules.
• Les mots de la phrase1 et de la phrase2 sont séparés par un seul espace.

Indice :

1. Une façon de voir les choses est de trouver une phrase comme une concaténation d'un préfixe et d'un suffixe de l'autre phrase.
2. Obtenez le préfixe commun le plus long entre eux et le suffixe commun le plus long.

Solution :

Nous pouvons l'approcher en comparant le préfixe et le suffixe communs les plus longs des deux phrases. Si les mots de la partie restante d'une phrase sont entièrement contenus dans l'autre phrase (éventuellement vide), alors les phrases peuvent être considérées comme similaires.

Mesures:

1. Divisez les deux phrases en tableaux de mots.
2. Utilisez deux pointeurs pour comparer le préfixe commun le plus long depuis le début des deux tableaux.
3. Utilisez deux autres pointeurs pour comparer le suffixe commun le plus long à partir de la fin des deux tableaux.
4. Après avoir comparé le préfixe et le suffixe communs, si les mots restants dans l'une des phrases forment un tableau vide (ce qui signifie qu'ils ont tous été mis en correspondance), alors les phrases sont considérées comme similaires.

Implémentons cette solution en PHP : 1813. Similarité des phrases III

/**


@param String $sentence1
@param String $sentence2
@return Boolean
/
function areSentencesSimilar($sentence1, $sentence2) {
...
...
...
/*


go to ./solution.php
*/
}





// Test examples

$sentence1 = "My name is Haley";

$sentence2 = "My Haley";

echo areSentencesSimilar($sentence1, $sentence2) ? 'true' : 'false'; // Output: true

$sentence1 = "of";

$sentence2 = "A lot of words";

echo areSentencesSimilar($sentence1, $sentence2) ? 'true' : 'false'; // Output: false

$sentence1 = "Eating right now";

$sentence2 = "Eating";

echo areSentencesSimilar($sentence1, $sentence2) ? 'true' : 'false'; // Output: true

?>





  

  

  Explication :





Diviser les phrases en mots : Nous utilisons éclater() pour diviser les chaînes de phrases en tableaux de mots.

Comparaison des préfixes communs : Nous parcourons les deux tableaux depuis le début et comparons les mots correspondants. La boucle continue tant que les mots correspondent.

Comparaison des suffixes communs : Nous comparons les mots de la fin des deux tableaux, encore une fois en utilisant une boucle pour vérifier les mots correspondants.

Vérification finale : Après avoir traité le préfixe et le suffixe communs, nous vérifions si le nombre de mots correspondants (suffixe de préfixe) couvre tous les mots de la phrase la plus courte. Si tel est le cas, les phrases peuvent être considérées comme similaires.



  
  
  Complexité temporelle :



La complexité temporelle est O(n m), où n et m sont respectivement les longueurs de la phrase1 et de la phrase2. En effet, nous traitons les mots des deux phrases une seule fois tout en vérifiant le préfixe et le suffixe communs.


Cette solution devrait fonctionner efficacement compte tenu des contraintes.

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!