Solving the LeetCode "Zigzag Conversion" Problem in Go

Difficulty: Medium | Tags: String

Introduction

The Zigzag Conversion problem requires transforming a given string into a zigzag pattern across a specified number of rows and then reading it row by row. This problem tests string manipulation skills and pattern recognition.

Problem Analysis

Given a string like "PAYPALISHIRING" and numRows = 3, the zigzag pattern is written as:

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

Reading row-wise gives "PAHNAPLSIIGYIR". The challenge is to simulate this pattern programmatically for any input string and row count.

Solution Approach

The solution involves tracking the direction of movement (down or up) and appending characters to the appropriate row. When reaching the first or last row, the direction reverses. The final result is obtained by concatenating all rows.

Go Implementation

func convert(s string, numRows int) string {
    if numRows == 1 {
        return s
    }
    rows := make([]string, numRows)
    currentRow := 0
    goingDown := false
    for _, char := range s {
        rows[currentRow] += string(char)
        if currentRow == 0 || currentRow == numRows-1 {
            goingDown = !goingDown
        }
        if goingDown {
            currentRow++
        } else {
            currentRow--
        }
    }
    var result string
    for _, row := range rows {
        result += row
    }
    return result
}

Complexity Analysis

Time Complexity: O(n), where n is the length of the string. Each character is processed exactly once.
Space Complexity: O(n), as we store all characters in rows before concatenation.

Testing and Examples

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

Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"

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

Best Practices and Tips

1. Handle the numRows = 1 case immediately to avoid unnecessary computations.
2. Use a boolean flag to track direction changes for cleaner code.
3. Pre-allocate rows if performance is critical, though Go's string concatenation is efficient for this problem.