Ajouter des espaces à une chaîne

2109. Ajouter des espaces à une chaîne

Difficulté :Moyen

Sujets : Tableau, deux pointeurs, chaîne, simulation

Vous recevez une chaîne s indexée à 0 et un tableau d'entiers indexés à 0 qui décrit les indices dans la chaîne d'origine où les espaces seront ajoutés. Chaque espace doit être inséré avant le caractère à l'index donné.

• Par exemple, étant donné s = "EnjoyYourCoffee" et espaces = [5, 9], nous plaçons des espaces avant 'Y' et 'C', qui sont respectivement aux indices 5 et 9. Ainsi, nous obtenons « Enjoy Your Coffee ».

Renvoyer la chaîne modifiée après les espaces ont été ajoutés.

Exemple 1 :

• Entrée : s = "LeetcodeHelpsMeLearn", espaces = [8,13,15]
• Sortie : "Leetcode m'aide à apprendre"
• Explication : Les indices 8, 13 et 15 correspondent aux caractères soulignés dans "LeetcodeHelpsMeLearn".
  • Nous plaçons ensuite des espaces avant ces caractères.

Exemple 2 :

• Entrée : s = "icodeinpython", espaces = [1,5,7,9]
• Sortie : "Je code en py thon"
• Explication : Les indices 1, 5, 7 et 9 correspondent aux caractères soulignés dans "icodeinpython".
  • Nous plaçons ensuite des espaces avant ces caractères.

Exemple 3 :

• Entrée : s = "espacement", espaces = [0,1,2,3,4,5,6]
• Sortie : " s p a c i n g "
• Explication : Nous sommes également capables de placer des espaces avant le premier caractère de la chaîne.

Contraintes :

• 1 5
• s se compose uniquement de lettres anglaises minuscules et majuscules.
• 1 5
• 0
• Toutes les valeurs des espaces sont strictement croissantes.

Indice :

1. Créez une nouvelle chaîne, initialement vide, comme chaîne modifiée. Parcourez la chaîne d'origine et ajoutez chaque caractère de la chaîne d'origine à la nouvelle chaîne. Cependant, chaque fois que vous atteignez un caractère qui nécessite un espace avant, ajoutez un espace avant d'ajouter le caractère.
2. Étant donné que le tableau d'index pour les emplacements d'espace est trié, utilisez un pointeur pour suivre l'index suivant pour placer un espace. N'incrémentez le pointeur qu'une fois qu'un espace a été ajouté.
3. Assurez-vous que votre opération d'ajout peut être effectuée en O(1).

Solution :

Nous pouvons utiliser une approche efficace avec deux indicateurs. Voici à quoi ressemblerait l'implémentation dans PHP 5.6 :

Explication de la solution :

1. Utilisez un pointeur spaceIndex pour suivre la position actuelle dans le tableau des espaces.
2. Parcourez la chaîne s à l'aide d'une boucle.
3. Vérifiez si l'index actuel dans la chaîne correspond à la valeur actuelle dans le tableau d'espaces. Si c'est le cas, ajoutez un espace au résultat et déplacez le pointeur spaceIndex vers l'avant.
4. Ajouter le caractère actuel de la chaîne au résultat.
5. Renvoyer le résultat final sous forme d'une seule chaîne.

Cette approche garantit que nous traitons efficacement les entrées, en tirant parti de l'ordre de tri du tableau d'espaces.

Implémentons cette solution en PHP : 2109. Ajouter des espaces à une chaîne

<?php /**
 * @param String $s
 * @param Integer[] $spaces
 * @return String
 */
function addSpaces($s, $spaces) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$s1 = "LeetcodeHelpsMeLearn";
$spaces1 = [8, 13, 15];
echo addSpaces($s1, $spaces1) . "\n"; // Output: "Leetcode Helps Me Learn"

// Example 2
$s2 = "icodeinpython";
$spaces2 = [1, 5, 7, 9];
echo addSpaces($s2, $spaces2) . "\n"; // Output: "i code in py thon"

// Example 3
$s3 = "spacing";
$spaces3 = [0, 1, 2, 3, 4, 5, 6];
echo addSpaces($s3, $spaces3) . "\n"; // Output: " s p a c i n g"
?>

Explication:

1. Ajout efficace :Le fichier . L'opérateur en PHP est utilisé pour ajouter des chaînes efficacement.
2. Deux pointeurs : Le pointeur spaceIndex garantit que nous ne traitons le tableau d'espaces qu'une seule fois.
3. Complexité temporelle :
   • L'itération sur la chaîne prend O(n), où n est la longueur de la chaîne.
   • La vérification par rapport au pointeur du tableau d'espaces prend O(m), où m est la longueur du tableau d'espaces.
   • Combiné : O(n m), ce qui est optimal compte tenu des contraintes.

Cette solution respecte les contraintes et est efficace même pour des apports importants.

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!