LeetCode Problem

Problem Description

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)

Examples

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

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

Constraints

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

Follow-up

Approach to Solve

Use a simulation approach to create the zigzag pattern and then read it row by row.

Code Implementation

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s
        rows = [''] * numRows
        current_row = 0
        step = 1
        for char in s:
            rows[current_row] += char
            if current_row == 0:
                step = 1
            elif current_row == numRows - 1:
                step = -1
            current_row += step
        return ''.join(rows)

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1 || s.length() <= numRows) return s;
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
        int currentRow = 0;
        boolean goingDown = false;
        for (char c : s.toCharArray()) {
            rows[currentRow].append(c);
            if (currentRow == 0 || currentRow == numRows - 1) goingDown = !goingDown;
            currentRow += goingDown ? 1 : -1;
        }
        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) result.append(row);
        return result.toString();
    }
}

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1 || s.length() <= numRows) return s;
        vector<string> rows(numRows);
        int currentRow = 0;
        bool goingDown = false;
        for (char c : s) {
            rows[currentRow] += c;
            if (currentRow == 0 || currentRow == numRows - 1) goingDown = !goingDown;
            currentRow += goingDown ? 1 : -1;
        }
        string result;
        for (string row : rows) result += row;
        return result;
    }
};

Explanation

This solution uses a simulation approach to create the zigzag pattern and then read it row by row. Here's a detailed explanation:

First, we handle edge cases: if numRows is 1 or greater than or equal to the length of the string, we return the original string as no conversion is needed.
We create an array of strings (or StringBuilder in Java) to represent each row of the zigzag pattern.
We iterate through each character in the input string:
- We add the current character to the current row.
- We change direction (going down or up) when we reach the top or bottom row.
- We move to the next row based on the current direction.
After processing all characters, we combine all rows into a single string and return it.

The time complexity is O(n) where n is the length of the input string, as we process each character once. The space complexity is also O(n) as in the worst case (when numRows is large), we store all characters in our rows array.

This approach efficiently simulates the zigzag pattern without actually creating a 2D grid, making it both time and space efficient.

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

LeetSolved

Zigzag Conversion