:orphan:

Zigzag Conversion
=================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/zigzag-conversion/

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``

.. highlight:: python

Pattern
-------
String

Solution
--------
Create a 2d array ``rows`` that is ``numRows`` rows by ``len(s)`` columns. The
zigzag pattern has 2 parts. The zig is a vertical line and the zag is diagonal.
Track whether we should be zigging or zagging with a boolean. When we reach the
top or bottom of ``rows``, switch from zig to zag or zag to zig. Iterate
through the string, setting a cell in rows to the current character. Join
``rows`` together row-wise to get the converted string.

Code
----

.. literalinclude:: ../problems/medium/zigzag-conversion/zigzag_conversion__approach_1.py
    :language: python
    :lines: 12-

Test
----
>>> from zigzag_conversion__approach_1 import convert
>>> convert('PAYPALISHIRING', 3)
'PAHNAPLSIIGYIR'
>>> convert('PAYPALISHIRING', 4)
'PINALSIGYAHRPI'
>>> convert('A', 1)
'A'

Complexity
----------
| :math:`n` is the length of the input string and :math:`m` is the number of rows.
| Time: :math:`O(n + m)` — pass through the string to build each row and then join them together
| Auxiliary Space: :math:`O(1)`

.. autofunction:: zigzag_conversion__approach_1.convert