006. ZigZag Conversion

1. 题目

See HERE.

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

2. 解题

2.1 c++

Cost: 12 ms (77.28%), 10.3 MB (81.48%)

class Solution {
public:
    string convert(string s, int numRows) {
        // a math problem, 我就是个天才233333
        // 将此题视为一个对周期问题求解的过程
        if (numRows <= 1) return s;
        string out;
        int row = 0, len = s.size(), period = 2 * numRows - 2;
        while (row < numRows){
            int first = row, second = period - row;
            for (int i = 0; i < len; i += period){
                if (i + first < len)
                    out.push_back(s[i + first]);
                if (second != first && second != period && i + second < len)
                    out.push_back(s[i + second]);
            }
            ++row;
        }
        return out;
    }
};

2.2 Python

Cost: 56 ms (84.93 %), 13.3 MB ()

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if s=='' or numRows>len(s) or numRows==1:
            return s
        zigzag = [''] * numRows
        ind, step = 0, 1
        for char in s:
            zigzag[ind] += char
            ind += step
            if ind == 0:
                step = 1
            elif ind == numRows-1:
                step = -1
        tar = ''
        for i in range(numRows):
            tar += zigzag[i]
        return tar