algoadvance

Leetcode 6. Zigzag Conversion

Problem Statement

The Zigzag Conversion problem can be described as follows:

Given a string s and a number of rows numRows, arrange the characters of the string in a zigzag pattern on the given number of rows, and then read the characters row by row.

For example, the string “PAYPALISHIRING” with numRows = 3 is arranged in a zigzag pattern as follows:

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

And the output string (reading it row by row) would be: "PAHNAPLSIIGYIR".

Clarifying Questions

  1. Input Constraints:
    • What is the length range of the input string?
    • What is the range of numRows?
  2. Edge Cases:
    • What should be the output if numRows is 1?
    • How should we handle an empty input string?

Code

Let’s implement this in Java:

public class ZigzagConversion {
    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();
    }

    public static void main(String[] args) {
        ZigzagConversion converter = new ZigzagConversion();
        System.out.println(converter.convert("PAYPALISHIRING", 3));  // Output: "PAHNAPLSIIGYIR"
        System.out.println(converter.convert("PAYPALISHIRING", 4));  // Output: "PINALSIGYAHRPI"
    }
}

Strategy

  1. Edge Cases Handling:
    • If numRows is 1 or if the length of the string s is less than or equal to numRows, return the string s as it is. This is because no zigzag pattern would need to be applied.
  2. Allocate Rows:
    • Use an array of StringBuilder to hold the characters for each row. Initialize each StringBuilder.
  3. Traverse the String:
    • Use a loop to traverse through each character of the string.
    • Determine the current row and the direction (either up or down) for placing characters.
    • Place characters accordingly in the respective StringBuilder objects.
  4. Combine Rows:
    • After populating characters in their respective rows, concatenate all rows and return the final result.

Time Complexity

This solution ensures that the characters are arranged and read in a zigzag pattern efficiently.

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