Leetcode journey - Question 6 - Zigzag Conversion

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)

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

Solution:

Approach:

After looking at the question, I thought of using a 2D array to store the characters in the zigzag pattern. But, I realized that it would be a waste of space. So, I thought of using a vector of strings to store the characters in the zigzag pattern. I used a boolean variable goingDown to keep track of the direction of the zigzag pattern. If goingDown is true, then I increment the row number. If goingDown is false, then I decrement the row number. I used a for loop to iterate through the string s. I used a if-else statement to check if the row number is 0 or numRows - 1. If it is, then I change the value of goingDown. I used a for loop to iterate through the vector of strings and append the characters to the string ans. I returned the string ans.

Let's look at the pseudo code:

function convert(s, numRows)
    if numRows is equal to 1
        return s  // as there will be no zigzag pattern
    create a vector of strings rows with size min(numRows, size of s)
    create an integer curRow and initialize it to 0
    create a boolean variable goingDown and initialize it to false
    for each character c in s
        append c to rows[curRow]
        if curRow is equal to 0 or curRow is equal to numRows - 1
            change the value of goingDown
        if goingDown is true
            increment curRow
        else
            decrement curRow
    create a string ans
    for each string row in rows
        append row to ans
    return ans
end function

Now, we can write the code:

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    string convert(string s, int numRows)
    {
        if (numRows == 1)
        {
            return s;
        }
        vector<string> rows(min(numRows, int(s.size())));
        int curRow = 0;
        bool goingDown = false;
        for (char c : s)
        {
            rows[curRow] += c;
            if (curRow == 0 || curRow == numRows - 1)
            {
                goingDown = !goingDown;
            }
            curRow += goingDown ? 1 : -1;
        }
        string ans;
        for (string row : rows)
        {
            ans += row;
        }
        return ans;
    }
};

int main()
{
    Solution s;
    cout << s.convert("PAYPALISHIRING", 3) << endl;
    return 0;
}

Complexity Analysis:

Time Complexity: O(n)
Space Complexity:O(n)
Hope this helps!

If you have any questions, please leave a comment below. 💭
If you like this article, please share it with your friends. 💖
If you want to read more articles like this, please follow me.