6. ZigZag Conversion #

Problem #

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= s.length <= 1000
• s consists of English letters (lower-case and upper-case), ',' and '.'.
• 1 <= numRows <= 1000

Problem Summary #

Arrange a given string s in a Z-shaped pattern from top to bottom and from left to right according to the given number of rows numRows.

For example, when the input string is "PAYPALISHIRING" and the number of rows is 3, the arrangement is as follows:

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

After that, your output needs to be read row by row from left to right, producing a new string, for example: "PAHNAPLSIIGYIR".

Please implement this function that transforms the string according to the specified number of rows:

string convert(string s, int numRows);

Solution Approach #

• This problem does not involve much algorithmic thinking; it tests the ability to control the program flow. Use 2 variables to store the direction. When the number of vertically output rows reaches the specified target number of rows, it needs to turn from bottom to top back to the first row. Control the directionji well in the loop.

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); {
		if down != numRows {
			matrix[down] = append(matrix[down], byte(s[i]))
			down++
			i++
		} else if up > 0 {
			matrix[up] = append(matrix[up], byte(s[i]))
			up--
			i++
		} else {
			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)
}