Fusionner les chaînes alternativement

Hey les codeurs ! J'espère que tu vas bien. Je suis ravi de partager mes solutions pour la série LeetCode-75, qui couvre 75 problèmes essentiels pour vous aider à vous préparer aux entretiens de codage.

Dans chaque article, je présenterai ma solution ainsi qu'une explication détaillée de mon approche. N'hésitez pas à laisser des questions ou des suggestions d'amélioration dans les commentaires. J'ai hâte de collaborer et de discuter avec vous ! Bon codage !

J'ai ajouté ici le lien pour le problème : Fusionner les chaînes en alternance

Description du problème

Vous recevez deux chaînes mot1 et mot2. Fusionnez les chaînes en ajoutant des lettres en ordre alterné, en commençant par mot1. Si une chaîne est plus longue que l'autre, ajoutez les lettres supplémentaires à la fin de la chaîne fusionnée.

Renvoie la chaîne fusionnée.

*Exemple 1 : *

Entrée : mot1 = "abc", mot2 = "pqr"
Sortie : "apbqcr"
Explication : La chaîne fusionnée sera fusionnée ainsi :
mot1 : a b c
mot2 : p q r
fusionné : a p b q c r

Exemple 2 :

Entrée : word1 = "ab", word2 = "pqrs"
Sortie : "apbqrs"
Explication : Notez que comme le mot2 est plus long, "rs" est ajouté à la fin.
mot1 : un b
mot2 : p q r s
fusionné :a p b q r s

** Exemple 3 :**

Entrée : mot1 = "abcd", mot2 = "pq"
Sortie : "apbqcd"
Explication : Notez que comme le mot1 est plus long, "cd" est ajouté à la fin.
mot1 : a b c d
mot2 : p q
fusionné : a p b q c d

SOLUTION

Intuition

Étant donné deux chaînes, nous devons les fusionner en alternant les caractères de chaque chaîne. La solution est simple si les deux chaînes ont la même longueur, mais elles peuvent avoir des longueurs différentes. Nous allons parcourir les deux chaînes à l'aide de pointeurs, en ajoutant des caractères au résultat jusqu'à ce que les deux pointeurs atteignent la fin.

Approche

1. Créez un StringBuilder pour stocker les caractères alternés des deux chaînes.
2. Créez deux pointeurs pour garder une trace de la position actuelle dans chaque chaîne.
3. Itérez les deux chaînes jusqu'à ce que les deux pointeurs atteignent la fin de leurs chaînes respectives.
4. Ajoutez des éléments au StringBuilder si la chaîne n'est pas vide et incrémentez le pointeur
5. Renvoyer le StringBuilder

Complexité

• Complexité temporelle :
  La complexité temporelle est O(n) où n est la longueur de la chaîne la plus longue, lorsque nous parcourons les chaînes.

• Complexité spatiale :
  La complexité temporelle est de 0(1) puisque nous utilisons un StringBuilder et quelques variables.

Code

  public String mergeAlternately (String word1, String word2) {
    // ? Create a StringBuilder to build the result string efficiently
    StringBuilder completeWord = new StringBuilder();

    // ? Initialize two pointers to traverse both strings
    int p1 = 0;
    int p2 = 0;

    // ? Iterate through both strings until both pointers reach the end of their resépectives strings
    while (p1 < word1.length() || p2 < word2.length()) {
      // ? Append the current character from words if the pointer is within bounds
      if (p1 < word1.length()) completeWord.append(word1.charAt(p1));
      if (p2 < word2.length()) completeWord.append(word2.charAt(p2));
      p1++;
      p2++;
    }
    // ? Convert the StringBuilder to a string and return it
    return completeWord.toString();
  }

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!