Zigzag Conversion

LeetCode 6 | Difficulty: Medium

Medium

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)

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

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

- `1 <= s.length <= 1000`

- `s` consists of English letters (lower-case and upper-case), `','` and `'.'`.

- `1 <= numRows <= 1000`

Topics: String

---

Approach

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 245 ms)

Metric	Value
Runtime	245 ms
Memory	N/A
Date	2017-07-24

Solution

public class Solution {
    public string Convert(string s, int numRows) {
    StringBuilder[] sb = new StringBuilder[numRows];
    int i = 0;
    int n = s.Length;
    for (int k = 0; k < numRows; k++)
    {
        sb[k] = new StringBuilder();
    }
    while (i < n)
    {
        for (int idx = 0; idx < numRows && i < n; idx++)
        {
            sb[idx].Append(s[i++]);
        }
        for (int idx = numRows-2; idx >= 1 && i<n; idx--)
        {
            sb[idx].Append(s[i++]);
        }
    }
    for (int idx = 1; idx < sb.Length; idx++)
    {
        sb[0].Append(sb[idx]);
    }
    return sb[0].ToString();
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.