algoadvance

Leetcode 6. Zigzag Conversion

Problem Statement

The “Zigzag Conversion” problem requires converting a given string into a zigzag pattern on a given number of rows. Here’s the formal description:

Given a string s and an integer numRows, arrange the characters of the string in a zigzag pattern across numRows rows. The pattern is such that reading the characters line by line would produce a sequence like how they naturally appear on the Z-shape.

For example, the string “PAYPALISHIRING” with numRows = 3 would look like:

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

And reading it line by line produces “PAHNAPLSIIGYIR”.

Clarifying Questions

  1. Q: Can the input string be empty? A: Yes, in such a case, the output should also be an empty string.

  2. Q: What should be the behavior if numRows is greater than the length of the string? A: In that case, the output should be the same as the input string.

  3. Q: What is the expected range of numRows? A: Typically, numRows will be between 1 and the length of the string.

Strategy

  1. Edge Cases: Handle cases where the string is empty or numRows is 1. In these scenarios, return the string as it is.
  2. Create Rows: Use a vector of strings to store the zigzag pattern for each row.
  3. Simulate Filling the Zigzag: Iterate through each character in the string, placing it in the correct row by simulating the zigzag traversal (downward direction, followed by upward direction).
  4. Concatenate Rows: Once all characters are placed, concatenate all rows to form the final zigzagged string.

Code

#include <string>
#include <vector>

std::string convert(std::string s, int numRows) {
    if (numRows == 1 || s.empty() || numRows >= s.size()) {
        return s;
    }
    
    std::vector<std::string> rows(numRows);
    int curRow = 0;
    bool goingDown = false;

    for (char c : s) {
        rows[curRow] += c;
        if (curRow == 0 || curRow == numRows - 1) {
            goingDown = !goingDown;
        }
        curRow += goingDown ? 1 : -1;
    }

    std::string result;
    for (const std::string& row : rows) {
        result += row;
    }

    return result;
}

Time Complexity

This approach ensures that we efficiently build the zigzag pattern and compose the desired output in optimal time.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI