Zigzag Conversion
LeetCode #6 · Medium · Strings · C++ solution with worked-out approach and complexity analysis.
Approach
Simulate the Zigzag Pattern
Key insight
Instead of building a 2D grid, we can use separate strings for each row and append characters as we traverse down and up the rows.
Time
O(n)
Space
O(n)
Problem description(from LeetCode)
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.
Examples
Example 1
- Input:
- s = "PAYPALISHIRING", numRows = 3
- Output:
- "PAHNAPLSIIGYIR"
Constraints
- •1 <= s.length <= 1000
- •s consists of English letters (lower-case and upper-case), ',' and '.'.
- •1 <= numRows <= 1000
C++ Solution
solution.cpp
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1 || s.size() <= numRows) return s;
vector<string> rows(numRows);
int currentRow = 0;
bool isGoingDown = false;
for (char c : s) {
rows[currentRow] += c;
if (currentRow == 0 || currentRow == numRows - 1) {
isGoingDown = !isGoingDown;
}
currentRow += isGoingDown ? 1 : -1;
}
string result;
for (string &row : rows) result += row;
return result;
}
};