Zigzag Conversion - C Solution

1. Introduction

This post discusses a string manipulation challenge known as the "Zigzag Conversion". The problem involves writing a given string in a zigzag pattern on a specified number of rows and then reading it line by line. It's a unique problem that tests the programmer's ability to handle string indices in a non-linear fashion.

Problem

Given a string s and an integer numRows, the task is to write the string in a zigzag pattern on numRows and then return the string as read line by line. For instance, "PAYPALISHIRING" written in a zigzag pattern on 3 rows reads "PAHNAPLSIIGYIR".

2. Solution Steps

1. Handle edge cases where numRows is 1 or less than the length of the string.

2. Create an array of strings, each representing a row in the zigzag pattern.

3. Iterate over the characters in s, calculating the appropriate row for each character and appending it to the corresponding string.

4. Concatenate all rows to form the final zigzag string.

5. Return the zigzag string.

3. Code Program

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Function to convert string to zigzag pattern
char* convert(char* s, int numRows) {
    if (numRows == 1 || numRows >= strlen(s)) {
        return s;
    }

    char** rows = (char**) malloc(numRows * sizeof(char*));
    for (int i = 0; i < numRows; i++) {
        rows[i] = (char*) malloc(strlen(s) + 1);
        rows[i][0] = '\0';
    }

    int currentRow = 0;
    int goingDown = 0;

    for (int i = 0; s[i] != '\0'; i++) {
        strcat(rows[currentRow], (char[]){s[i], '\0'});
        if (currentRow == 0 || currentRow == numRows - 1) goingDown = !goingDown;
        currentRow += goingDown ? 1 : -1;
    }

    char* result = (char*) malloc(strlen(s) + 1);
    result[0] = '\0';

    for (int i = 0; i < numRows; i++) {
        strcat(result, rows[i]);
        free(rows[i]);
    }

    free(rows);
    return result;
}

// Main function to test the convert function
int main() {
    char s1[] = "PAYPALISHIRING";
    char* r1 = convert(s1, 3);
    printf("Zigzag Conversion (Example 1): %s\n", r1);
    free(r1);

    char s2[] = "PAYPALISHIRING";
    char* r2 = convert(s2, 4);
    printf("Zigzag Conversion (Example 2): %s\n", r2);
    free(r2);

    char s3[] = "A";
    char* r3 = convert(s3, 1);
    printf("Zigzag Conversion (Example 3): %s\n", r3);
    free(r3);

    return 0;
}

Output:

Zigzag Conversion (Example 1): PAHNAPLSIIGYIR
Zigzag Conversion (Example 2): PINALSIGYAHRPI
Zigzag Conversion (Example 3): A

Explanation:

1. Handle edge cases where the zigzag pattern is unnecessary.

2. Create an array of strings to represent each row in the zigzag pattern.

3. Iterate over s, appending characters to the appropriate row.

4. Switch direction at the top and bottom rows.

5. Concatenate all rows to get the final string.

6. Free the allocated memory for each row and the rows array.

7. The main function tests the convert function with three examples and prints the zigzag converted strings.