6. ZigZag Conversion

Đề bài

Chuỗi "PAYPALISHIRING" được viết theo dạng zích zắc (zigzag) trên một số hàng cho trước như sau (nên hiển thị bằng font monospace để dễ nhìn):

P   A   H   N
A P L S I I G
Y   I   R

Sau đó đọc theo từng dòng (từ trên xuống dưới): "PAHNAPLSIIGYIR"

Hãy viết hàm nhận vào chuỗi và số hàng, rồi trả về chuỗi sau khi chuyển đổi:

string convert(string s, int numRows);

Ví dụ 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Ví dụ 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Ví dụ 3:

Input: s = "A", numRows = 1
Output: "A"

Ràng buộc:

• 1 <= s.length <= 1000
• s chỉ gồm chữ cái tiếng Anh (chữ thường và chữ hoa), dấu ',' và dấu '.'
• 1 <= numRows <= 1000

Tóm tắt đề

Với một chuỗi s và số hàng numRows, hãy sắp xếp các ký tự của s theo dạng chữ Z (zigzag): đi từ trên xuống, rồi chéo lên, lặp lại cho tới hết chuỗi.

Ví dụ với "PAYPALISHIRING" và numRows = 3, ta có:

P   A   H   N
A P L S I I G
Y   I   R

Cuối cùng, đọc từng dòng từ trái sang phải để tạo chuỗi mới, ví dụ: "PAHNAPLSIIGYIR"。

Hãy hiện thực hàm chuyển đổi theo số hàng đã cho:

string convert(string s, int numRows);

Ý tưởng

• Bài này chủ yếu kiểm tra khả năng mô phỏng đúng quy luật đi zích zắc.
• Một cách làm trực quan: dùng 2 pha di chuyển:
  • Đi thẳng xuống từ hàng 0 → hàng numRows-1
  • Đi chéo lên từ hàng numRows-2 → hàng 1 Lặp lại hai pha này cho tới khi dùng hết ký tự.
• Trong code bên dưới, ta dùng 2 biến down và up để điều khiển hai pha, và dùng một mảng matrix (mỗi hàng là một slice) để gom ký tự theo từng dòng, rồi nối lại.

Code

package leetcode

func convert(s string, numRows int) string {
	matrix, down, up := make([][]byte, numRows, numRows), 0, numRows-2
	for i := 0; i != len(s); {
		// Pha 1: đi thẳng xuống (0 -> numRows-1)
		if down != numRows {
			matrix[down] = append(matrix[down], byte(s[i]))
			down++
			i++
		// Pha 2: đi chéo lên (numRows-2 -> 1)
		} else if up > 0 {
			matrix[up] = append(matrix[up], byte(s[i]))
			up--
			i++
		} else {
			// Reset để bắt đầu một chu kỳ zigzag mới
			up = numRows - 2
			down = 0
		}
	}
	solution := make([]byte, 0, len(s))
	for _, row := range matrix {
		for _, item := range row {
			solution = append(solution, item)
		}
	}
	return string(solution)
}

---