1768. Merge Strings Alternately

Easy
Description

給定兩個字串 word1 和 word2，交替合併字元。若某字串較長，將剩餘字元接在結果尾端。

Example:

Input: word1 = “abc”, word2 = “pqr” Output: “apbqcr”

Intuition#

核心思路：用一個指針同時遍歷兩個字串，每步輪流加入字元，短的結束後把長的剩餘部分接上。

  • 經典的合併 / zip 操作
  • 雙指針或單指針皆可，關鍵是處理好長度不同的情況

Approaches#

1: 逐字元交替 + 補尾#

  • 概念: 用一個 index 走到較短字串結束，交替加入字元；再把較長字串剩餘部分接上
  • 時間複雜度: O(n + m) - n, m 分別為兩字串長度
  • 空間複雜度: O(n + m) - 結果字串
class Solution {
    fun mergeAlternately(word1: String, word2: String): String {
        val sb = StringBuilder()
        var i = 0
        while (i < word1.length || i < word2.length) {
            if (i < word1.length) sb.append(word1[i])
            if (i < word2.length) sb.append(word2[i])
            i++
        }
        return sb.toString()
    }
}

⭐2: Two Pointers（分別追蹤）#

  • 概念: 分別用兩個指針追蹤兩字串位置，用 boolean 旗標輪流切換
  • 時間複雜度: O(n + m)
  • 空間複雜度: O(n + m)
class Solution {
    fun mergeAlternately(word1: String, word2: String): String {
        val sb = StringBuilder()
        var p1 = 0
        var p2 = 0
        while (p1 < word1.length && p2 < word2.length) {
            sb.append(word1[p1++])
            sb.append(word2[p2++])
        }
        while (p1 < word1.length) sb.append(word1[p1++])
        while (p2 < word2.length) sb.append(word2[p2++])
        return sb.toString()
    }
}

兩種寫法本質相同，Approach 2 更清楚地分離了「交替區段」與「剩餘區段」。

🔑 Takeaways#

  • Pattern: 雙指針平行遍歷兩個序列
  • 關鍵技巧: 類似 Merge Two Sorted Lists 的框架，交替取元素後處理剩餘部分