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 <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5char* convert(char* s, int numRows) {
6 if (numRows == 1) return s;
7 int len = strlen(s);
8 char** rows = (char**)malloc(sizeof(char*) * numRows);
9 for (int i = 0; i < numRows; i++) {
10 rows[i] = (char*)malloc(sizeof(char) * len);
11 rows[i][0] = '\0';
12 }
13 int currentRow = 0, step = 1;
14 for (int i = 0; i < len; i++) {
15 strncat(rows[currentRow], &s[i], 1);
16 if (currentRow == 0) step = 1;
17 else if (currentRow == numRows - 1) step = -1;
18 currentRow += step;
19 }
20 char* result = (char*)malloc(sizeof(char) * (len + 1));
21 result[0] = '\0';
22 for (int i = 0; i < numRows; i++) {
23 strcat(result, rows[i]);
24 free(rows[i]);
25 }
26 free(rows);
27 return result;
28}The C solution implements a zigzag pattern simulation by creating an array of strings for each row. As we iterate through the input string, we add characters to the respective row. When we reach the top or bottom, we reverse direction. Finally, we concatenate all rows to produce the result.
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.
1def The Python approach calculates which characters should be included in which order directly using their indices, optimizing to bypass simulation and leveraging cycle-based index computation.