Cantumkan Rentetan Bergantian

Hei pengekod! Harap awak sihat. Saya teruja untuk berkongsi penyelesaian saya untuk siri LeetCode-75, yang merangkumi 75 masalah penting untuk membantu anda bersedia untuk temu duga pengekodan.

Dalam setiap siaran, saya akan membentangkan penyelesaian saya bersama-sama dengan penjelasan terperinci tentang pendekatan saya. Jangan ragu untuk meninggalkan sebarang soalan atau cadangan untuk penambahbaikan dalam ulasan. Saya tidak sabar-sabar untuk bekerjasama dan berbincang dengan anda! Selamat Mengekod!

Saya telah menambah di sini pautan untuk masalah: Gabung Rentetan Bergantian

Penerangan masalah

Anda diberi dua rentetan perkataan1 dan perkataan2. Cantumkan rentetan dengan menambah huruf dalam susunan berselang-seli, bermula dengan perkataan1. Jika rentetan lebih panjang daripada rentetan yang lain, tambahkan huruf tambahan pada hujung rentetan yang digabungkan.

Kembalikan rentetan dicantumkan.

*Contoh 1: *

Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Penjelasan: Rentetan yang digabungkan akan digabungkan sedemikian:
perkataan1: a b c
perkataan2: p q r
digabungkan: a p b q c r

Contoh 2:

Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Penjelasan: Perhatikan bahawa kerana perkataan2 lebih panjang, "rs" dilampirkan pada penghujungnya.
perkataan1: a b
perkataan2: p q r s
digabungkan: a p b q r s

** Contoh 3:**

Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Penjelasan: Perhatikan bahawa kerana perkataan1 lebih panjang, "cd" dilampirkan pada penghujungnya.
perkataan1: a b c d
perkataan2: p q
digabungkan: a p b q c d

PENYELESAIAN

Intuisi

Memandangkan dua rentetan, kita perlu menggabungkannya dengan menukar aksara daripada setiap rentetan. Penyelesaiannya adalah mudah jika kedua-dua rentetan mempunyai panjang yang sama, tetapi mereka boleh mempunyai panjang yang berbeza. Kami akan mengulangi kedua-dua rentetan menggunakan penuding, menambah aksara pada hasil sehingga kedua-dua penuding mencapai penghujung.

Pendekatan

1. Buat StringBuilder untuk menyimpan aksara bergantian daripada kedua-dua rentetan.
2. Buat dua penunjuk untuk menjejaki kedudukan semasa dalam setiap rentetan.
3. Lelaran kedua-dua rentetan sehingga kedua-dua penunjuk mencapai penghujung rentetan masing-masing.
4. Tambahkan elemen pada StringBuilder jika rentetan tidak kosong dan naikkan penunjuk
5. Kembalikan StringBuilder

Kerumitan

• Kerumitan masa:
  Kerumitan masa ialah O(n) dengan n ialah panjang rentetan yang lebih panjang, sambil kita mengulangi rentetan itu.

• Kerumitan ruang:
  Kerumitan masa ialah 0(1) kerana kami menggunakan StringBuilder dan beberapa pembolehubah.

Kod

  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();
  }

Atas ialah kandungan terperinci Cantumkan Rentetan Bergantian. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!