給定兩個字串
word1和word2，交替合併字元。若某字串較長，將剩餘字元接在結果尾端。
Example:
Input: word1 = “abc”, word2 = “pqr” Output: “apbqcr”
Intuition
TIP
核心思路：用一個指針同時遍歷兩個字串，每步輪流加入字元，短的結束後把長的剩餘部分接上。
- 經典的合併 / zip 操作
- 雙指針或單指針皆可，關鍵是處理好長度不同的情況
Approaches
1. Alternate Chars + Append Tail — O(n + m) / O(n + m)
- Idea: 用一個 index 走到較短字串結束，交替加入字元；再把較長字串剩餘部分接上
- Time:
O(n + m)- n, m 分別為兩字串長度 - Space:
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 (track separately) — O(n + m) / O(n + m)
- Idea: 分別用兩個指針追蹤兩字串位置，用 boolean 旗標輪流切換
- Time:
O(n + m) - Space:
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()
}
}WARNING
兩種寫法本質相同，Approach 2 更清楚地分離了「交替區段」與「剩餘區段」。
🔑 Takeaways
- Pattern: 雙指針平行遍歷兩個序列
- Key trick: 類似 Merge Two Sorted Lists 的框架，交替取元素後處理剩餘部分