6. Zigzag Conversion

Medium

Description

將字串按照 Z 字形（鋸齒形）排列在指定行數上，然後逐行讀取。例如 “PAYPALISHIRING” 在 3 行時排列為： P A H N A P L S I I G Y I R

Example:

Input: s = “PAYPALISHIRING”, numRows = 3 Output: “PAHNAPLSIIGYIR”

Intuition#

核心思路：模擬 Z 字形的上下移動，將每個字元分配到對應的行，最後按行拼接。

字元在行之間的移動像彈球：0 -> 1 -> 2 -> … -> numRows-1 -> numRows-2 -> … -> 0
可以用一個方向變數控制向下或向上移動
也可以找出數學規律直接計算每行的字元索引

Approaches#

⭐1: 模擬逐行分配#

概念: 用 numRows 個 StringBuilder 模擬各行，遍歷字串時在行間上下移動
時間複雜度: O(n) - 遍歷字串一次
空間複雜度: O(n) - 儲存結果

class Solution {
    fun convert(s: String, numRows: Int): String {
        if (numRows == 1 || numRows >= s.length) return s

        val rows = Array(numRows) { StringBuilder() }
        var currRow = 0
        var goingDown = false

        for (ch in s) {
            rows[currRow].append(ch)
            // 在首行或末行時改變方向
            if (currRow == 0 || currRow == numRows - 1) {
                goingDown = !goingDown
            }
            currRow += if (goingDown) 1 else -1
        }

        return rows.joinToString("") { it.toString() }
    }
}

2: 數學索引法#

概念: 直接計算每行字元在原字串中的索引，週期為 2 * numRows - 2
時間複雜度: O(n)
空間複雜度: O(n)

class Solution {
    fun convert(s: String, numRows: Int): String {
        if (numRows == 1 || numRows >= s.length) return s

        val sb = StringBuilder()
        val cycle = 2 * numRows - 2

        for (row in 0 until numRows) {
            var i = row
            while (i < s.length) {
                sb.append(s[i])
                // 中間行有額外的斜線字元
                if (row != 0 && row != numRows - 1) {
                    val diagonal = i + cycle - 2 * row
                    if (diagonal < s.length) {
                        sb.append(s[diagonal])
                    }
                }
                i += cycle
            }
        }

        return sb.toString()
    }
}

🔑 Takeaways#

Pattern: 方向變數模擬往返移動——碰到邊界就反向
關鍵技巧: 週期為 2 * numRows - 2；中間行每個週期有兩個字元（直下和斜上），首尾行只有一個