LeetCode ZigZag Conversion: 2 Different Angles

Overvew

Analyze the solutions from two different angles to solve the LeetCode ZigZag Convension problem: from index of original string to zigzag one or vise verse.

LeetCode 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 text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Two Different Angles Solution

(1) A simple way (not very interesting) to solve this LeetCode Zigzag Conversion problem is to simulate the Zigzag process: we allocate an array of strings of size nRows, each string in which corresponds to a row in the zigzag one, then linear scan the input string, we can easily figure out the current character is in which row by keeping a step variable and rest this step when encountering the first row or the last row. So this is linear scan the ORIGINAL STRING.

(2) Linear scan the Zigzag string and for the current character index i, we try to identify, the corresponding index i’ in the original string and put that correct character into the final zigzag string. So this is from a reversed angle, more details are listed as follows:

The key here is to figure out the index pattern, just draw several concrete example could hele:

nRow = 2:

0 2 4 6 8 10 12
1 3 5 7 9 11 13

nRow = 3: 

0     4      8     12 
1  3  5   7  9  11
2     6     10

nRow = 4:
0      6       12
1   5  7    11 13
2 4    8  10
3      9

So inorder to get the final string, we need to scan from the left to right row by row, for the first and last row, the difference
between every two is 2 * nRow – 2, and for the middle say i-th rows, the difference between every two is either 2 * nRow – 2 – 2 * i
or 2 * i in turn. Following this, a linear scan of the original string could give us the final result string by pushing the corresponding character  at specific index into the final resulted string. The source code accepted by LeetCode OJ to pass the Zigzag conversion problem is as follows:

string convert(string s, int nRows) {
    int n = s.size(); 
    if (nRows <= 1 || nRows >= n) return s;
    int gap    = ((nRows - 1) << 1);
    int gapTmp = 0;
    int next = 0;
    string ret;
    for (int i = 0; i < nRows; ++i) {
        ret.push_back(s[i]); 
        if (i != nRows - 1)
            gapTmp = ((nRows - i - 1) << 1);
        else 
            gapTmp = gap;
        next = i + gapTmp;
        while (next < n) {
            ret.push_back(s[next]);
            if (i != 0 && i != nRows - 1)
                gapTmp = gap - gapTmp;
            next = next + gapTmp;
        }
    }
    return ret;
}

Summary

I analyzed the solutions from two different angles to solve the LeetCode ZigZag Convension problem: from index of original string to zigzag one or vise verse.

Written on May 6, 2013