Zigzag Conversion LeetCode Solution

Problem Statement

Zigzag Conversion LeetCode Solution – 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);

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

Explanation

The size of every period is defined as a “cycle”

cycle = (2*nRows - 2), except nRows == 1.


In this example, (2*nRows – 2) = 4.

In every period, every row has 2 elements, except the first row and the last row.

Suppose the current row is i, the index of the first element is j:

j = i + cycle*k, k = 0, 1, 2, ...


The index of the second element is secondJ:

secondJ = (j - i) + cycle - i


(j-i) is the start of the current period, (j-i) + cycle is the start of the next period.

Pseudocode:

1. check for edge-case (numRows = 1)
2. initialize the array of StringBuffers.
3. append each character in the input string to correct StringBuffer according to the fluctuating index
4. concatenate all the StringBuffers to one and return the concatenation

Notes:

1. StringBuffers are better than Strings when we have heavy string manipulation
2. We will implement a fluctuating index discussed below that implements the zigzag characteristic

Main idea:
We create an array (of size numRows) of StringBuffers. Then, we add each character at position i of the input string to the StringBuffer at an index that fluctuates between 0 and numRows – 1. Finally, we can concatenate all the StringBuffers to one StringBuffer and return that concatenation. The most important concepts are (1) that there will be an index that will fluctuate between 0 and numRows – 1 that will simulate the zigzag conversion and (2) we will have an array of StringBuffers that will be accessed in a zigzag manner according to that fluctuating index.

For example, if numRows = 4 and the string is “AMAZONISHIRING”
idx -> 0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 2, …
i -> 0, 1, 2, 3, 4, 5, 6, 7, …

So,
A is appended to the StringBuffer at idx 0 of the array of StringBuffers
M is appended to the StringBuffer at idx 1 of the array of StringBuffers
A -> array[2]
Z -> array[3]
O -> array[2]
N -> array[1]

Code

C++ Code for Zigzag Conversion

class Solution {
public:
    string convert(string s, int numRows) {
        string result="";
        if(numRows==1)
      return s;
        int step1,step2;
        int len=s.size();
        for(int i=0;i<numRows;++i){
            step1=(numRows-i-1)*2;
            step2=(i)*2;
            int pos=i;
            if(pos<len)
                result+=s.at(pos);
            while(1){
                pos+=step1;
                if(pos>=len)
                    break;
        if(step1)
          result+=s.at(pos);
                pos+=step2;
                if(pos>=len)
                    break;
        if(step2)
          result+=s.at(pos);
            }
        }
        return result;
    }
};

Java Code for Zigzag Conversion

class Solution {
    public String convert(String s, int numRows) {
        String ans="";
        if(numRows==1) return s;
        for (int i=0;i<numRows;i++) {
            int incr=2*(numRows-1);
            for (int j=i;j<s.length();j+=incr) {
                ans+=s.charAt(j);
                if(i>0 && i<numRows-1 && j+incr-(2*i)<s.length()) ans+=s.charAt(j+incr-(2*i));
            } 
        }
        return ans;
    }
}

Complexity Analysis for Zigzag Conversion LeetCode Solution

Time Complexity

O(n)

Space Complexity

O(1)