Zigzag Conversion - CPP Solution

1. Introduction

This blog post addresses an interesting string manipulation problem known as the Zigzag Conversion. The challenge is to write a string in a zigzag pattern on a given number of rows and then read it line by line. This problem tests one's ability to use data structures and logic in C++ effectively.

Problem

Given a string, we are required to write it in a zigzag pattern on a specified number of rows and then read it line by line. For example, the string "PAYPALISHIRING" written in a zigzag pattern over 3 rows would look like this:

P A H N

A P L S I I G

Y I R

The converted string read line by line would be "PAHNAPLSIIGYIR". The task is to implement a function:

string convert(string s, int numRows);

2. Solution Steps

1. Create an array of strings, one for each row.

2. Iterate through the given string, adding each character to the appropriate row.

3. Use a variable to keep track of the current row and a boolean to indicate the direction of zigzagging (up or down).

4. Toggle the direction each time the top or bottom row is reached.

5. After the iteration, concatenate all strings from the array to get the final converted string.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to convert a string into a zigzag pattern on given number of rows
string convert(string s, int numRows) {
    if (numRows == 1) return s; // No zigzag for single row

    vector<string> rows(min(numRows, int(s.size())));
    int curRow = 0;
    bool goingDown = false;

    // Iterate over each character in the string
    for (char c : s) {
        rows[curRow] += c; // Add character to the current row
        if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown; // Change direction
        curRow += goingDown ? 1 : -1; // Move up or down
    }

    // Concatenate all rows to form the final string
    string ret;
    for (string row : rows) ret += row;
    return ret;
}

int main() {
    string str = "PAYPALISHIRING";
    cout << "Converted string: " << convert(str, 3) << endl;
    return 0;
}

Output:

Converted string: PAHNAPLSIIGYIR

Explanation:

1. The input string "PAYPALISHIRING" is written in a zigzag pattern over 3 rows.

2. Each character is placed in the appropriate row based on the current direction of zigzagging.

3. The direction changes whenever the top or bottom row is reached.

4. After placing all characters, the rows are concatenated.

5. The final converted string, read line by line, is "PAHNAPLSIIGYIR".