algoadvance

The “Zigzag Conversion” problem on LeetCode is as follows: Convert a given string s to a new string in a “zigzag” pattern, given a specified number of rows, numRows.

Here’s an example of how the conversion works with s = "PAYPALISHIRING" and numRows = 4:

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

The output for this example would be “PINALSIGYAHRPI”.

Requirements:

Clarifying Questions:

  1. What should be returned if numRows is 1?
    • Since there is only one row, the zigzag pattern is the string itself.
  2. Can the string be empty?
    • Yes, and the returned result should be an empty string.
  3. How large can the string s be?
    • Typically, strings in LeetCode problems can be very large, but Python handles large strings efficiently; thus, we can assume a lengthy input.

Strategy

  1. If numRows is 1 or the length of the string is less than numRows, return the string itself as there is no “zigzag” possible.
  2. Initialize an array to store strings for each row.
  3. Use a variable to track the current row and another variable to determine the direction (down or up).
  4. Traverse through the string character by character, appending each character to the appropriate row based on the current direction.
  5. Once the current row reaches the top or bottom, change the direction and continue.
  6. Finally, join all the rows to create the zigzag string.

Code

def convert(s: str, numRows: int) -> str:
    if numRows == 1 or numRows >= len(s):
        return s

    # Initialize the rows
    rows = [''] * numRows
    curRow = 0
    goingDown = False

    # Traverse the string character by character
    for char in s:
        rows[curRow] += char
        if curRow == 0 or curRow == numRows - 1:
            goingDown = not goingDown
        curRow += 1 if goingDown else -1

    # Combine the rows
    return ''.join(rows)

# Example usage
s = "PAYPALISHIRING"
numRows = 4
result = convert(s, numRows)
print(result)  # Expected "PINALSIGYAHRPI"

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string s. This is because we process each character in the string exactly once.

The space complexity is O(n) as well, since we are storing intermediate results for each of the rows in the list, and then concatenating these at the end to create the final result.

Let me know if you need further clarifications or modifications!

Try our interview co-pilot at AlgoAdvance.com