back to list

ZigZag Conversion

Medium

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.

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

The easiest way to solve this problem would seem to be to just place all the letters in "buckets" made for each row. Let's take a look at that solution. First lets start with the skeleton function from leetcode.

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
   
};

We will need to keep track of our "buckets" of letters. We also need to create one bucket for each row.

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    let results = []
    for (let i = 0; i < numRows; i++) {
        results.push("");
    }
};

We will also need to keep track of what row we are collecting letters for. Since we will be using this in a for loop we will start the row counter at 0.

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    let results = []
    for (let i = 0; i < numRows; i++) {
        results.push("");
    }
    let row = 0
};

One final thing we need to track before we start looping through our input string is the direction that we art going in our rows. Since we are alternating back and forth from the first row (started at 0) and the last row, which is the numRows - 1 (since we started our count at 0) we can basically have a toggle between adding 1 and subtracting 1. We can initiate it with a value of - 1 for now.

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    let results = []
    for (let i = 0; i < numRows; i++) {
        results.push("");
    }
    let row = 0
    let direction = -1
};

We can now set up our loop to iterate over the input string.

var convert = function(s, numRows) {
    let results = []
    for (let i = 0; i < numRows; i++) {
        results.push("");
    }
    let row = 0
    let direction = -1
   
    for (let i = 0; i < s.length; i++) {
        
    }
};

Inside the loop we go through the letters adding them to the current rows "bucket".

var convert = function(s, numRows) {
    let results = []
    for (let i = 0; i < numRows; i++) {
        results.push("");
    }
    let row = 0
    let direction = -1

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

    }
};

Next we need to determine if we should change direction. We already mentioned that we should do that at row 0 and the numRows - 1. We can just toggle our direction by multiplying it by -1.

var convert = function(s, numRows) {
    let results = []
    for (let i = 0; i < numRows; i++) {
        results.push("");
    }
    let row = 0
    let direction = -1

   
    for (let i = 0; i < s.length; i++) {
        results[row] = results[row] + s[i]
        if (row === 0 || row === numRows - 1) {
            direction = direction * - 1
        }
    }
};

We are now just able to add that to our current row which will increment the row up until the last row, then decrement it back down to 0 and so on.

var convert = function(s, numRows) {
    let results = []
    for (let i = 0; i < numRows; i++) {
        results.push("");
    }
    
    let row = 0
    let direction = -1
   
    for (let i = 0; i < s.length; i++) {
        results[row] = results[row] + s[i]
        if (row === 0 || row === numRows - 1) {
            direction = direction * - 1
        }
        row += direction
    }
};

We can finally return back the buckets by joining them together to make our final string.

var convert = function(s, numRows) {
    let results = []
    for (let i = 0; i < numRows; i++) {
        results.push("");
    }
    let row = 0
    let direction = -1
   
    for (let i = 0; i < s.length; i++) {
        results[row] = results[row] + s[i]
        if (row === 0 || row === numRows - 1) {
            direction = direction * - 1
        }
        row += direction
    }
    return results.join("") 
};

One thing to think about is if there are any special cases hat we can avoid all the looping and building up of letters into "buckets". For instance if the numRows is 1, we know that the input string is the correct output string. We will add that to the very top of our unction call so we can return early in that case.

var convert = function(s, numRows) {
    if (numRows === 1) return s
    let results = []
    for (let i = 0; i < numRows; i++) {
        results.push("");
    }
    

    let row = 0
    let direction = -1
   
    for (let i = 0; i < s.length; i++) {
        results[row] = results[row] + s[i]
        if (row === 0 || row === numRows - 1) {
            direction = direction * - 1
        }
        row += direction
    }
    return results.join("")
};