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.
1varIn JavaScript, this method optimizes the zigzag extraction by calculating the index for each row directly and iterating based on the computed cycle length for a direct string generation.