Algorithm Puzzles: ZigZag Conversion

Posted on Edited on In Views: Word count in article: 488 Reading time ≈ 2 mins.

Algorithm Puzzles everyday every week sometimes: ZigZag Conversion

Puzzle

Puzzle from leetcode:

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)

1
2
3
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:

1
2
3
4
P     I    N
A   L S  I G
Y A   H R
P     I

Solution

First came out solution

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

It’s obvious that the output is periodic for first row:

1
2
3
0 = 2 * (numRows - 1) * 0
6 = 2 * (numRows - 1) * 1
12 = 2 * (numRows - 1) * 2

Let T = 2 * (numRows - 1), for next row(row[1]):

1
2
3
4
5
1 = T * 0 + 1 
5 = T * 1 - 1
7 = T * 1 + 1
11 = T * 2 - 1
13 = T * 2 + 1

For row[2]:

1
2
3
4
2 = T * 0 + 2
4 = T * 1 - 2
8 = T * 1 + 2
...

Change 1,2 to rowIndex which start from 0 to numRows - 1 :

1
2
3
0 = T * 0 + rowIndex (rowIndex = 0)
1 = T * 0 + rowIndex (rowIndex = 1)
2 = T * 0 + rowIndex (rowIndex = 2)

Cool, can start coding now

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public:
    std::string convert(std::string s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        std::string res;
        size_t maxLength = s.size();
        size_t T = 2 * (numRows - 1);
        for (size_t rowIndex = 0; rowIndex < numRows; ++rowIndex) {
            size_t oriIndex = rowIndex;

            while (oriIndex < maxLength) {
                res.push_back(s[oriIndex]);
                size_t insertOne = oriIndex + T - rowIndex - rowIndex;
                if (insertOne > oriIndex && insertOne < oriIndex + T &&
                    insertOne < maxLength) {
                    res.push_back(s[insertOne]);
                }

                oriIndex += T;
            }
        }
        return res;
    }
};

Result:

Let’s do some optimization:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public:
    const std::string convert(const std::string& s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        std::string res;
        size_t maxLength = s.size();
        size_t T = 2 * (numRows - 1);
        for (size_t rowIndex = 0; rowIndex < numRows; ++rowIndex) {
            size_t oriIndex = rowIndex;

            while (oriIndex < maxLength) {
                res.push_back(s[oriIndex]);
                size_t insertOne = oriIndex + T - rowIndex - rowIndex;
                if (insertOne > oriIndex && insertOne < oriIndex + T &&
                    insertOne < maxLength) {
                    res.push_back(s[insertOne]);
                }

                oriIndex += T;
            }
        }
        return std::move(res);
    }
};

Result:

Looks like we also can change size_t T = 2 * (numRows - 1) to size_t T = numRows + numRows -2 to use add instead of multiply

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public:
    const std::string convert(const std::string& s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        std::string res;
        size_t maxLength = s.size();
        size_t T = (numRows + numRows - 2);
        for (size_t rowIndex = 0; rowIndex < numRows; ++rowIndex) {
            size_t oriIndex = rowIndex;

            while (oriIndex < maxLength) {
                res.push_back(s[oriIndex]);
                size_t insertOne = oriIndex + T - rowIndex - rowIndex;
                if (insertOne > oriIndex && insertOne < oriIndex + T &&
                    insertOne < maxLength) {
                    res.push_back(s[insertOne]);
                }

                oriIndex += T;
            }
        }
        return std::move(res);
    }
};

Result:

Super, better than 99.34% now!