Leetcode Study Day 11

Zigzag Conversion

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: “PAHNAPLSIIGYIR”

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I
Example 3:

Input: s = "A", numRows = 1
Output: "A"
 

Constraints:

1 <= s.length <= 1000
s consists of English letters (lower-case and upper-case), ',' and '.'.
1 <= numRows <= 1000

Solution

I asked chatGPT for help and it shows me the pseudo code and the idea:

Let’s first understand the pattern of the zigzag.

For numRows = 3, the sequence of rows for the characters is: 0, 1, 2, 1, 0, 1, 2, 1, 0...

For numRows = 4, the sequence is: 0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 2, 1, 0...

So, the pattern is basically to increment the row number from 0 to numRows - 1, then decrement it back to 0, and repeat.

Given this understanding, you can approach this problem using the following steps:

1. Initialize an array of strings rows of size numRows.
2. Iterate through each character of the input string s.
3. For each character, determine its row in the zigzag pattern and append it to the corresponding row’s string in the rows array.
4. Finally, concatenate all the rows to get the final result.

Here’s the pseudocode:

function convert(s, numRows):
    if numRows == 1:
        return s

    rows = array of empty strings of size numRows
    currentRow = 0
    direction = -1  // -1 for moving up, 1 for moving down

    for each character c in s:
        rows[currentRow] += c

        // Change direction if we're at the top or bottom
        if currentRow == 0 or currentRow == numRows - 1:
            direction *= -1

        currentRow += direction

    result = concatenate all strings in rows
    return result

Here’s the corresponding C++ code:

string convert(string s, int numRows) {
    if (numRows == 1) return s;
    
    vector<string> rows(min(numRows, int(s.size())));
    int currentRow = 0;
    int direction = -1;  // -1 for moving up, 1 for moving down

    for (char c : s) {
        rows[currentRow] += c;

        if (currentRow == 0 || currentRow == numRows - 1) {
            direction *= -1;
        }

        currentRow += direction;
    }

    string result;
    for (string row : rows) {
        result += row;
    }
    return result;
}