6. Zigzag Conversion

Description of the Problem

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)

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

Solution

Explanation

The solution is less intutive. Consider the following example: \[ \begin{matrix} x_0 & & & & & x_{10} & & & & & x_{20} \\ x_1 & & & & x_9 & x_{11} & & & & x_{19} & x_{21} \\ x_2 & & & x_8 & & x_{12} & & & x_{18} & & . \\ x_3 & & x_7 & & & x_{13} & & x_{17} & & & . \\ x_4 & x_6 & & & & x_{14} & x_{16} & & & & . \\ x_5 & & & & & x_{15} & & & & & . \\ \end{matrix} \]

Without consider extra characters of each row, the interval of index of two consecutive characters in a row is 2 * (num_rows - 1) (e.g. [x_0, x_10, x_20] and [x_1, x_11, x_21]).

\[ \begin{matrix} x_0 & & & & & x_{10} & & & & & x_{20} \\ x_1 & & & & \_ & x_{11} & & & & \_ & x_{21} \\ x_2 & & & \_ & & x_{12} & & & \_ & & . \\ x_3 & & \_ & & & x_{13} & & \_ & & & . \\ x_4 & \_ & & & & x_{14} & \_ & & & & . \\ x_5 & & & & & x_{15} & & & & & . \\ \end{matrix} \]

Then, consider the extra characters in the middle rows, the index of these characters are (offset - r) where offset is the interval multiplied by an integer k (i.e. interval * k), r is index of the row (i.e. 0 to n-1).

\[ \begin{matrix} x_0 & & & & & x_{10} & & & & & x_{20} \\ x_1 & & & & x_{10-1} & x_{11} & & & & x_{20-1} & x_{21} \\ x_2 & & & x_{10-2} & & x_{12} & & & x_{20-2} & & . \\ x_3 & & x_{10-3} & & & x_{13} & & x_{20-3} & & & . \\ x_4 & x_{10-4} & & & & x_{14} & x_{20-4} & & & & . \\ x_5 & & & & & x_{15} & & & & & . \\ \end{matrix} \]

Now, the solution is to append characters according to row number and index.

Code (Rust)

impl Solution {
    pub fn convert(s: String, num_rows: i32) -> String {

        let num_rows = num_rows as usize;
        let n = s.len();

        if num_rows == 1 {
            return s;
        }

        let mut result = vec![];
        let char_array = s.as_bytes();

        for r in 0..num_rows {
            let mut offset = 0;
            while r + offset < n {
                result.push(char_array[r+offset]);
                offset += 2*(num_rows - 1);
                if 1 <= r && r <= num_rows - 2 && offset < n + r {
                    result.push(char_array[offset-r]);
                }
            }
        }

        return String::from_utf8(result).unwrap();
    }
}

Complexity (n is the length of string s)

Time complexity:

  • \(O(n)\)

Auxiliary Space:

  • \( O(n) \)