Sponsored
Sponsored
This approach involves simulating the zigzag pattern by using an array of strings to represent each row. We iterate through the string, placing each character in the appropriate row based on the current direction (down or up in the zigzag pattern). We change the direction whenever we hit the top or bottom row.
Time Complexity: O(n), where n represents the length of the input string, as we iterate through the string once.
Space Complexity: O(n), to store the zigzag rows.
1#include <string>
2#include <vector>
3
4std::string convert(std::string s, int numRows) {
5 if (numRows == 1 || numRows >= s.length()) return s;
6 std::vector<std::string> rows(numRows);
7 int currentRow = 0;
8 bool goingDown = false;
9 for (char c : s) {
10 rows[currentRow] += c;
11 if (currentRow == 0 || currentRow == numRows - 1) goingDown = !goingDown;
12 currentRow += goingDown ? 1 : -1;
13 }
14 std::string result;
15 for (std::string row : rows) result += row;
16 return result;
17}The C++ solution uses a vector of strings to simulate the zigzag pattern. We toggle the direction whenever the current row reaches the top or bottom. The result is obtained by concatenating all rows together.
This approach calculates the regular intervals for placing characters in the zigzag pattern without simulating the full grid. By deducing the mathematical relation of indices, characters are stored directly in the result string.
Time Complexity: O(n), where n is the input string length, owing to a complete pass through the characters.
Space Complexity: O(n), needed for the output string.
1
This C solution calculates the correct indices for zigzag order dynamically. By understanding the repetitive cycle length, it extracts characters directly in order. The outer loop runs over each row index, and within it, character indices are calculated for the zigzag transformation.