Alkesh

LeetCode - ZigZag Conversion

Problem statement

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);

Problem statement taken from: https://leetcode.com/problems/zigzag-conversion

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

Explanation

Process by row

The number of rows into which the string should be zig-zag is passed. We can create an array of strings. Based on the current index, append that character in the respective string array index.

Let's check the algorithm.

- if numRows <= 1
  - return s

- initialize i, set row = 0, down = true

- initialize array of strings: string array[numRows]

- loop for i = 0; i < numRows; i++
  - set array[i] = "" (empty string)

- loop for i = 0; i < s.size(); i++
  - append character to string
    array[row] += s[i];

  - if row == 0
    - set down = true

  - if row == numRows - 1
    - set down = false

  - increment or decrement row based on down boolean
    down ? row++ : row--

- set string answer = ""

- loop for i = 0; i < numRows; i++
  - answer += array[i]

- return answer

C++ solution

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows <= 1) {
            return s;
        }

        int i, row = 0;
        bool down = true;
        string array[numRows];

        for(i = 0; i < numRows; i++){
            array[i] = "";
        }

        for(i = 0; i < s.size(); i++){
            array[row] += s[i];

            if(row == 0){
                down = true;
            }

            if(row == numRows - 1){
                down = false;
            }

            down ? row++ : row--;
        }

        string answer = "";

        for(i = 0; i < numRows; i++){
            answer += array[i];
        }

        return answer;
    }
};

Golang solution

func convert(s string, numRows int) string {
    if numRows <= 1 {
        return s
    }

    i, row := 0, 0
    down := true
    array := make([]string, numRows)

    for i = 0; i < len(s); i++ {
        array[row] += string(s[i])

        if row == 0 {
            down = true
        }

        if row == numRows - 1 {
            down = false
        }

        if down {
            row++
        } else {
            row--
        }
    }

    answer := ""

    for i = 0; i < numRows; i++ {
        answer += array[i]
    }

    return answer
}

Javascript solution

var convert = function(s, numRows) {
    if( numRows <= 1 ){
        return s;
    }

    let i, row = 0;
    let down = true;
    let array = [];

    for( i = 0; i < numRows; i++ ){
        array[i] = "";
    }

    for( i = 0; i < s.length; i++ ){
        array[row] += s[i];

        if( row == 0 ){
            down = true;
        }

        if( row == numRows - 1 ){
            down = false;
        }

        down ? row++ : row--;
    }

    var answer = "";

    for( i = 0; i < numRows; i++ ){
        answer += array[i];
    }

    return answer;
};

Let's dry-run our algorithm to see how the solution works.

Input: s = "ABCDEFGH", numRows = 3

Step 1: if numRows <= 1
          3 <= 1
          false

Step 2: int i, row = 0
        bool down = true
        string array[numRows]
        string array[3];

Step 3: loop for i = 0; i < numRows; i++
          - set array[i] = "";

        numRows = 3
        so array[0] = array[1] = array[2] = ""

Step 4: loop for i = 0; i < s.size()
        i < 8
        0 < 8
        true

        array[row] += s[i]
        array[row] = array[0] + s[0]
                   = "" + "A"
                   = "A"
        array[0] = "A"

        row == 0
        true
        down = true

        down ? row++ : row--
        row++
        row = 1

        i++
        i = 1

Step 5: loop for i < s.size()
        i < 8
        1 < 8
        true

        array[row] += s[i]
        array[row] = array[1] + s[1]
                   = "" + "B"
                   = "B"
        array[1] = "B"

        row == 0
        false

        row == numRows - 1
        1 == 2
        false

        down ? row++ : row--
        row++
        row = 2

        i++
        i = 2

Step 6: loop for i < s.size()
        i < 8
        2 < 8
        true

        array[row] += s[i]
        array[row] = array[2] + s[2]
                   = "" + "C"
                   = "C"
        array[2] = "C"

        row == 0
        false

        row == numRows - 1
        2 == 2
        true
        down = false

        down ? row++ : row--
        row--
        row = 1

        i++
        i = 3

Step 7: loop for i < s.size()
        i < 8
        3 < 8
        true

        array[row] += s[i]
        array[row] = array[1] + s[3]
                   = "B" + "D"
                   = "BD"
        array[1] = "BD"

        row == 0
        false

        row == numRows - 1
        1 == 2
        false

        down ? row++ : row--
        row--
        row = 0

        i++
        i = 4

Step 8: loop for i < s.size()
        i < 8
        4 < 8
        true

        array[row] += s[i]
        array[row] = array[0] + s[4]
                   = "A" + "E"
                   = "AE"
        array[1] = "AR"

        row == 0
        true
        down = true

        row == numRows - 1
        1 == 2
        false

        down ? row++ : row--
        row++
        row = 1

        i++
        i = 5

Step 9: loop for i < s.size()
        i < 8
        5 < 8
        true

        array[row] += s[i]
        array[row] = array[1] + s[5]
                   = "BD" + "F"
                   = "BDF"
        array[1] = "BDF"

        row == 0
        false

        row == numRows - 1
        1 == 2
        false

        down ? row++ : row--
        row++
        row = 2

        i++
        i = 6

Step 10: loop for i < s.size()
        i < 8
        6 < 8
        true

        array[row] += s[i]
        array[row] = array[2] + s[6]
                   = "C" + "G"
                   = "CG"
        array[2] = "CG"

        row == 0
        false

        row == numRows - 1
        2 == 2
        true
        down = false

        down ? row++ : row--
        row--
        row = 1

        i++
        i = 7

Step 11: loop for i < s.size()
        i < 8
        7 < 8
        true

        array[row] += s[i]
        array[row] = array[1] + s[7]
                   = "BDF" + "H"
                   = "BDFH"
        array[1] = "BDFH"

        row == 0
        false

        row == numRows - 1
        1 == 2
        false

        down ? row++ : row--
        row--
        row = 0

        i++
        i = 8

Step 11: loop for i < s.size()
        i < 8
        8 < 8
        false

Step 12: string answer = "";

Step 13: loop for( i = 0; i < numRows; i++ )
           answer += array[i];

        array[0] = "AE"
        array[1] = "BDFH"
        array[2] = "CG"

        so answer is "AEBDFHCG"

Step 14: return answer

So the answer is "AEBDFHCG"
Share this post!