Skip to content

Zigzag Conversion⚓︎

Link

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)

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

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⚓︎

Way 1 (Easy)⚓︎

 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
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows < 2) return s;

        vector<string> rows(numRows);
        int i = 0, flag = -1;

        for (char ch : s) {
            rows[i].push_back(ch);
            if (i == 0 || i == numRows - 1) {
                flag = -flag;
            }
            i += flag;
        }

        string res;
        for (const string& row : rows) {
            res += row;
        }


        return res;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(n)\).

Way 2⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        string res;

        for (int i = 0; i < numRows; i++) {
            if (i == 0 || i == numRows - 1) {
                for (int j = i; j < s.size(); j += 2 * numRows - 2) {
                    res += s[j];
                }
            } else {
                for (int j = i, k = 2 * numRows - 2 - i; 
                    j < s.size() || k < s.size(); 
                    j += 2 * numRows - 2, k += 2 * numRows - 2) {
                    if (j < s.size()) res += s[j];
                    if (k < s.size()) res += s[k];
                }
            }
        }

        return res;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(1)\).