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.
1public class Solution {
2 public String convert(String s, int numRows) {
3 if (numRows == 1 || numRows >= s.length()) return s;
4 StringBuilder[] rows = new StringBuilder[numRows];
5 for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
6 int currentRow = 0;
7 boolean goingDown = false;
8 for (char c : s.toCharArray()) {
9 rows[currentRow].append(c);
10 if (currentRow == 0 || currentRow == numRows - 1) goingDown = !goingDown;
11 currentRow += goingDown ? 1 : -1;
12 }
13 StringBuilder result = new StringBuilder();
14 for (StringBuilder row : rows) result.append(row);
15 return result.toString();
16 }
17}The Java solution models the zigzag pattern by using an array of StringBuilders. As each character is processed, it is added to the current row, and the direction is toggled at the boundaries. The final result is formed by appending 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.