6. Zigzag Conversion

 

Zigzag Conversion
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
Approach 1) Brute Force array

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    if(s == null || numRows <= 0){
        return;
    }
    if(numRows ==1){
        return s
    }
    
    let result = "";
    let steps = 2 * numRows - 2;
    for(let i=0; i<numRows; i++){
        for(let j=i; j < s.length; j += steps){
            result+=s[j];
            if(i != 0 && i != numRows - 1 && (j + steps - 2 * i) < s.length){
                console.log("ith",i);
                console.log("jth",(j + steps - 2 * i));
                result+=s[j + steps - 2 * i];
            }
        }
    }
    return result;
};


/*
Formula:

for first and last row : 2 * numRows - 2;
other = j + stpes - 2 * i;

[00]P                               [06]I                               [12]N
[01]A                   [05]L       [07]s                   [11]I       [13]G
[02]Y       [04]A                   [08]H       [10]R
[03]P                               [09]I

In our case - step = 2 * numRows - 2 = 2 * 4 - 2 = 6 and you can confirm that this condition holds true for first (0 —> 6 —> 12) and last rows (3 —> 9).

Iteration
For i = 0 => j = 0, 6, 12
For i = 1 => j = 1, 7, 13
For i = 2 => j = 2, 8
For i = 3 => j = 3, 9

*/

Approach 2) Multi-dimensional array
In this solution, we loop through the input string’s letters, and store each one in a multi-dimensional array that visually represents the eventual ZigZag. We do this by keeping a couple of markers: currentRow and headingDown. What these two markers do, is they enable us to keep track of which row should get the next letter, and whether we should head up or down after processing that letter. Once we then head up or down, we check if we’ve exceeded the size of the ZigZag, and then flip to head in the other direction. In other words, we zig-zag through the string!

What we end up with is a multi-dimensional array very similar to the data presented above. For example, here’s the “DUNCANMCARDLE” output:
[
  [ 'D', 'M', 'E' ],
  [ 'U', 'N', 'C', 'L' ],
  [ 'N', 'A', 'A', 'D' ],
  [ 'C', 'R' ]
]


With this output, we can then simply .join() each row, and concatenate them all together, to get our intended output.

Let`s Code IT!

var convert = function (inputString, targetRows) {
    if (targetRows == 1) {
        return inputString;
    }

    // Start the process on row 1, heading down
    let currentRow = 1;
    let headingDown = true;

    // Initialise an array to store the zigzag data
    let zigZagArray = [];

    // Loop through the requested number of rows
    for (let i = 0; i < targetRows; i++) {
        // Initialise each zigzag row as an empty array
        zigZagArray[i] = [];
    }

    // Loop through the string
    for (let i = 0; i < inputString.length; i++) {
        // Add the current letter to the current row
        zigZagArray[currentRow - 1].push(inputString[i]);

        if (headingDown) {
            currentRow++;

            // Check if we've exceeded the maximum number of rows
            if (currentRow > targetRows) {
                // Start heading back up again
                currentRow = targetRows - 1;
                headingDown = false;
            }
        } else {
            currentRow--;

            // Check if we've exceeded the top row
            if (currentRow < 1) {
                // Start heading down again
                currentRow = 2;
                headingDown = true;
            }
        }
    }

    // Initialise a return string
    let totalString = '';

    // Loop through the constructed rows
    for (let i = 0; i < targetRows; i++) {
        // Append the row's characters joined together
        totalString += zigZagArray[i].join('');
    }

    return totalString;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #6. Zigzag Conversion
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!