2825. Faire de la chaîne une sous-séquence en utilisant des incréments cycliques

difficulté: medium

sujets: deux pointeurs, string

vous avez deux 0 indexé Strings Str1 et str2.

Dans une opération, vous sélectionnez un set des indices dans str1, et pour chaque index i dans l'ensemble, incrément str1 [i] au caractère suivant cycliquement . C'est-à-dire 'a' devient 'b', 'b' devient 'c', et ainsi de suite, et 'z' devient 'a'.

return 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 autrement .

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

Exemple 1:

• entrée: str1 = "abc", str2 = "ad"
• output: true
• Explication: Sélectionnez l'index 2 dans STR1.
  • incrément str1 [2] pour devenir 'd'.
  • Par conséquent, Str1 devient "ABD" et STR2 est maintenant une sous-séquence. Par conséquent, vrai est renvoyé.

Exemple 2:

• entrée: str1 = "zc", str2 = "ad"
• output: true
• Explication: Sélectionnez les indices 0 et 1 dans STR1.
  • incrément str1 [0] pour devenir 'a'.
  • incrément str1 [1] pour devenir 'd'.
  • Par conséquent, STR1 devient "AD" et STR2 est maintenant une sous-séquence. Par conséquent, vrai est renvoyé.

Exemple 3:

• entrée: str1 = "ab", str2 = "d"
• output: false
• Explication: Dans cet exemple, il peut être démontré qu'il est impossible de faire de STR2 une sous-séquence de STR1 en utilisant le plus une fois.
  • Par conséquent, false est renvoyé.

contraintes:

• 1 5
• 1 5
• STR1 et STR2 se composent uniquement de lettres d'anglais minuscules.

Indice:

1. Considérons les indices que nous incrémentons séparément.
2. Nous pouvons maintenir deux pointeurs: pointeur I pour str1 et pointeur j pour str2, tout en veillant à ce qu'ils restent dans les limites des cordes.
3. Si STR1 [I] et STR2 [J] correspondent, ou si l'incrémentation STR1 [I] correspond à Str2 [J], nous augmentons les deux pointeurs; Sinon, nous n'incrémentons que 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 que nous ne pouvons plus trouver 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ément cyclique sur tous les caractères de STR1:

Explication:

• nous utiliserons deux pointeurs, i pour str1 et j pour str2.
• Si le personnage de str1 [i] correspond à str2 [j], nous avançons les deux pointeurs vers l'avant.
• Si str1 [i] peut être incrémenté pour correspondre à str2 [j] (cycliquement), nous essayons de les faire correspondre puis de déplacer les deux pointeurs.
• Si aucune des conditions ci-dessus ne peut, nous ne déplaçons que le pointeur I pour str1.
• Enfin, si nous pouvons 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 dans php: 2825. Faire de String une sous-séquence en utilisant des incréments cycliques

Explication:

1. deux pointeurs : i et j sont initialisés au début de str1 et str2, respectivement.
2. correspondant à la logique : à 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 correspondre à str2 [j] cycliquement.
   • La condition d'incrément cyclique est gérée en utilisant (ord ($ str1 [$ i]) 1 - ord ('a'))% 26 qui vérifie si str1 [i] peut être incrémentée pour correspondre à str2 [j].
3. Vérification de la sous-séquence : Si nous avons complètement itéré à STR2 (c'est-à-dire j == m), cela signifie que STR2 est une sous-séquence de STR1. Sinon, ce n'est pas le cas.

Complexité du temps:

• L'algorithme itère via STR1 une fois, et chaque caractère de Str2 n'est vérifié qu'une seule fois, donc la complexité de temps est o (n) , où n est la longueur de str1.

Complexité de l'espace:

• La complexité de l'espace est o (1) puisque nous n'utilisons que quelques pointeurs et n'avons pas besoin d'espace supplémentaire dépendant 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ément cyclique.

liens de contact

Si vous avez trouvé cette série utile, veuillez envisager de donner le référentiel une étoile sur GitHub ou de partager le message sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi!

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

• linkedIn
• github