ZigZag Conversion ใน C++ (แปลง String เป็นรูป ZigZag)

โจทย์ปัญหา

ได้รับ String และจำนวนแถว (numRows) ให้เขียน String ในรูปแบบ ZigZag แล้วอ่านแถวต่อแถวเพื่อสร้าง String ใหม่

ตัวอย่าง

นำเข้า: "IWANTTOLEARNCODE", numRows = 3

รูปแบบ ZigZag:

I       T       A       O
W   N   O   E   R   C   D
A       L       N       E

อ่านแถวต่อแถว: "ITAOWNOERCDALNE"

แนวคิดการแก้ปัญหา

จำลองการเคลื่อนที่ ZigZag โดยใช้:

• Array of Strings rows[numRows] เก็บตัวอักษรแต่ละแถว
• ตัวแปร currentRow (0 ถึง numRows-1)
• ตัวแปร goingDown (bool) บ่งบอกทิศทาง

อัลกอริทึม:

1. ถ้า numRows = 1 คืน String เดิม
2. สร้าง Array of Strings ขนาด numRows
3. วนลูปแต่ละตัวอักษรใน String:
   • เพิ่มตัวอักษรเข้า rows[currentRow]
   • อัปเดตทิศทาง: ถ้าอยู่แถวบนสุด (0) → goingDown = true; ถ้าอยู่แถวล่างสุด (numRows-1) → goingDown = false
   • อัปเดต currentRow: goingDown ? currentRow++ : currentRow--
4. รวม Strings ทุกแถวเข้าด้วยกัน

โค้ดตัวอย่าง (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;

        vector<string> rows(numRows);
        int currentRow = 0;
        bool goingDown = false;

        for (char c : s) {
            rows[currentRow].push_back(c);

            // เปลี่ยนทิศทางที่ขอบ
            if (currentRow == 0 || currentRow == numRows - 1)
                goingDown = !goingDown;

            currentRow += goingDown ? 1 : -1;
        }

        string result;
        for (const string& row : rows)
            result += row;

        return result;
    }
};

int main() {
    Solution ob;
    cout << ob.convert("IWANTTOLEARNCODE", 3) << endl;
    cout << ob.convert("PAYPALISHIRING", 3) << endl;  // PAHNAPLSIIGYIR
    cout << ob.convert("PAYPALISHIRING", 4) << endl;  // PINALSIGYAHRPI
    return 0;
}

ผลลัพธ์

ITAOWNOERCDALNE
PAHNAPLSIIGYIR
PINALSIGYAHRPI

คำอธิบายเพิ่มเติม

• ความซับซ้อนด้านเวลา: O(n) (n = ความยาว String)
• ความซับซ้อนด้านพื้นที่: O(n) สำหรับเก็บผลลัพธ์
• รูปแบบ ZigZag มี Cycle ยาว 2 * numRows - 2 ตัวอักษร (ยกเว้น numRows=1)
• สามารถ Optimize ได้โดยคำนวณ Index โดยตรงโดยไม่ต้องเก็บ Rows (Mathematical Approach)

รูปแบบ Index ทางคณิตศาสตร์ (Optional)

สำหรับ Row r (0-indexed):

• Row แรก (r=0): Index = k * cycle
• Row สุดท้าย (r=numRows-1): Index = k * cycle + (numRows-1)
• Row กลาง: Index = k * cycle + r และ k * cycle + (cycle - r)

โดย cycle = 2 * numRows - 2