Faire d'une chaîne une sous-séquence à l'aide d'incréments cycliques

2825. Faire d'une chaîne une sous-séquence à l'aide d'incréments cycliques

Difficulté :Moyen

Sujets : Deux pointeurs, chaîne

Vous recevez deux chaînes indexées à 0 str1 et str2.

Dans une opération, vous sélectionnez un ensemble d'indices dans str1, et pour chaque index i dans l'ensemble, incrémentez str1[i] au caractère suivant cycliquement. Autrement dit, « a » devient « b », « b » devient « c », et ainsi de suite, et « z » devient « a ».

Renvoyer true s'il est possible de faire de str2 une sous-séquence de str1 en effectuant l'opération au plus une fois, et false sinon.

Remarque : Une sous-séquence d'une chaîne est une nouvelle chaîne formée à partir de la chaîne d'origine en supprimant certains (éventuellement aucun) des caractères sans perturber les positions relatives des caractères restants.

Exemple 1 :

• Entrée : str1 = "abc", str2 = "ad"
• Sortie : vrai
• Explication : Sélectionnez l'index 2 dans str1.
  • Incrémentez str1[2] pour devenir 'd'.
  • Par conséquent, str1 devient "abd" et str2 est maintenant une sous-séquence. Par conséquent, true est renvoyé.

Exemple 2 :

• Entrée : str1 = "zc", str2 = "ad"
• Sortie : vrai
• Explication : Sélectionnez les indices 0 et 1 dans str1.
  • Incrémentez str1[0] pour devenir 'a'.
  • Incrémentez str1[1] pour devenir 'd'.
  • Par conséquent, str1 devient "ad" et str2 est maintenant une sous-séquence. Par conséquent, true est renvoyé.

Exemple 3 :

• Entrée : str1 = "ab", str2 = "d"
• Sortie : faux
• Explication : Dans cet exemple, on peut montrer qu'il est impossible de faire de str2 une sous-séquence de str1 en utilisant l'opération au plus une fois.
  • Par conséquent, false est renvoyé.

Contraintes :

• 1 5
• 1 5
• str1 et str2 sont constitués uniquement de lettres anglaises minuscules.

Indice :

1. Considérez les indices que nous incrémenterons séparément.
2. Nous pouvons conserver deux pointeurs : le pointeur i pour str1 et le pointeur j pour str2, tout en nous assurant qu'ils restent dans les limites des chaînes.
3. Si str1[i] et str2[j] correspondent, ou si l'incrémentation de str1[i] correspond à str2[j], nous augmentons les deux pointeurs ; sinon, nous incrémentons uniquement le pointeur i.
4. Il est possible de faire de str2 une sous-séquence de str1 si j est à la fin de str2, après on ne trouve plus de correspondance.

Solution :

Nous devons vérifier si nous pouvons faire de str2 une sous-séquence de str1 en effectuant au plus une opération d'incrémentation cyclique sur n'importe quel caractère de str1 :

Explication:

• Nous utiliserons deux pointeurs, i pour str1 et j pour str2.
• Si le caractère str1[i] correspond à str2[j], nous avançons les deux pointeurs.
• Si str1[i] peut être incrémenté pour correspondre à str2[j] (cycliquement), nous essayons de les faire correspondre puis déplaçons les deux pointeurs.
• Si aucune des conditions ci-dessus n'est remplie, nous déplaçons uniquement le pointeur i pour str1.
• Enfin, si nous pouvons faire correspondre tous les caractères de str2, alors il est possible de faire de str2 une sous-séquence de str1, sinon non.

Implémentons cette solution en PHP : 2825. Faire d'une chaîne une sous-séquence à l'aide d'incréments cycliques

<?php /**
 * @param String $str1
 * @param String $str2
 * @return Boolean
 */
function canMakeSubsequence($str1, $str2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage
$str1 = "abc";
$str2 = "ad";
echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: true

$str1 = "zc";
$str2 = "ad";
echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: true

$str1 = "ab";
$str2 = "d";
echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: false
?>

Explication:

1. Deux pointeurs : i et j sont initialisés respectivement au début de str1 et str2.
2. Matching Logic : à l'intérieur de la boucle, nous vérifions si les caractères de str1[i] et str2[j] sont les mêmes ou si nous pouvons incrémenter str1[i] pour faire correspondre str2[j] de manière cyclique.
   • La condition d'incrémentation cyclique est gérée à l'aide de (ord($str1[$i]) 1 - ord('a')) % 26 qui vérifie si str1[i] peut être incrémenté pour correspondre à str2[j].
3. Vérification de la sous-séquence : Si nous avons parcouru str2 complètement (c'est-à-dire j == m), cela signifie que str2 est une sous-séquence de str1. Sinon, ce n'est pas le cas.

Complexité temporelle :

• L'algorithme parcourt str1 une fois, et chaque caractère de str2 n'est vérifié qu'une seule fois, donc la complexité temporelle est O(n), où n est la longueur de str1.

Complexité spatiale :

• La complexité de l'espace est O(1) puisque nous n'utilisons que quelques pointeurs et n'avons pas besoin d'espace supplémentaire en fonction de la taille d'entrée.

Cette solution vérifie efficacement s'il est possible de faire de str2 une sous-séquence de str1 avec au plus une opération d'incrémentation cyclique.

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!