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
Solutions
Solution 1: Simulation
We use a 2D array \(g\) to simulate the process of arranging the string in a zigzag pattern, where \(g[i][j]\) represents the character at row \(i\) and column \(j\). Initially, \(i = 0\). We also define a direction variable \(k\), initially \(k = -1\), which means moving upwards.
We traverse the string \(s\) from left to right. For each character \(c\), we append it to \(g[i]\). If \(i = 0\) or \(i = \textit{numRows} - 1\), it means the current character is at a turning point in the zigzag pattern, so we reverse the value of \(k\), i.e., \(k = -k\). Then, we update \(i\) to \(i + k\), which means moving up or down one row. Continue traversing the next character until the end of the string \(s\). Finally, we return the concatenation of all rows in \(g\) as the result.
The time complexity is \(O(n)\) and the space complexity is \(O(n)\), where \(n\) is the length of the string \(s\).