6. ZigZag Conversion

问题描述

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

给定一个字符串s以及数字numRows，将字符串蛇形排列，最后将排列结果返回。

当前行row，行数numRows：

1. 当row < numRows，字符依次向下排列；
2. 当row == numRows-1,进入最后一行，接下来该往上排列；直到第一行，此时进入第1步。

解法

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows < 2) return s;
        string* arr = new string[numRows];
        int row = 0, step = 1;
        
        for (int i=0; i< s.size(); i++){
            arr[row].push_back(s[i]);
            
            if (row == 0) step = 1;//step用于控制是向上or向下
            else if (row == numRows - 1) step = -1;
            
            row += step;
        }
        string result;
        for (int i=0; i< numRows; i++)
            result += arr[i];
        
        return result;
    }
};