N字形变换的解题方法是把字母排列成Z字形的规律找出来。

先定义n=s.length()，n是字符串中字符的数量。

第一种想法是用二维矩阵把字母按照Z字形存放起来。设这个二维矩阵的行数为r，r=numRows，列数c和字母循环的周期有关。通过试验可以找到字母从上到下从左往右排列的循环周期t1跟Z字形的行数numRows有关，t=2*numRows-2，接下来计算有多少个t，t的数目t_num=n/t或者t_num=n/t+1，加一是向上取整，因为可能存在最后一个周期没有填满字符。一个周期t占用r-2+1列，二维矩阵总列数c=t_num*(r-1)。

接下来遍历字符串时如果字符串的下标i%t<r-1成立，则字符沿着二维数组当前列向下填充，否则就向右上方填充。具体代码如下：

class Solution {
public:
    string convert(string s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r >= n) {
            return s;
        }
        int t = r * 2 - 2;
        int t_num=n%t==0?n/t:n/t+1;
        int c=t_num*(r-1);
        vector<string>vec(r,string(c,0));
        for (int i = 0,x=0,y=0; i < n; ++i) {
            vec[x][y]=s[i];
            if(i%t<r-1){
                ++x;
            }
            else {
                --x;
                ++y;
            }
        }
        string ans;
        for(int i=0;i<r;i++)
            for(int j=0;j<c;j++)
                if(vec[i][j])ans+=vec[i][j];

        return ans;
    }
};

这总方法时间复杂度是O(r*c)，空间复杂度O(r*c)。能通过测试用例，但是时间和空间复杂度都比较高。

 

第二种方法是第一种方法的改进版。第二种方法把二位矩阵改为numRows行字符串，通过压缩掉未使用的空间减少浪费。因为原来的二维矩阵的很多位置没有被利用，遍历的时候浪费时间和空间。通过观察得知有一些列只存放一个字符，并且每一行都只是向当前字符串的末尾追加一个字符，所以只需要在不同的行之前切换，不需要考虑每一列。代码如下：

class Solution {
public:
    string convert(string s, int numRows) {
        int l=s.length();
        if(numRows<=1||numRows>=l)return s;
        int t=2*numRows-2;
        int num_t=l%t==0?l/t:l/t+1;  //周期数目
        int c=num_t*(numRows-1);  //列数
        vector<string>vec(numRows);
        for(int i=0,x=0;i<l;++i){
            vec[x]+=s[i];
            if(i%t<numRows-1){
                ++x;
            }
            else{
                --x;
            }
        }
        string str_z;
        for(int i=0;i<numRows;i++)
                str_z=str_z+vec[i];
           
        return str_z;
    }
};

 

第三种方法是利用数学规律找出字符下标和周期之间的关系，关系如图所示：

从左往右看每一行，会发现同一个周期内的第一个元素和第二元素分别满足j+i、j+t-i，并且j每次自增t。代码如下：

class Solution {
public:
    string convert(string s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r >= n) {
            return s;
        }
        string ans;
        int t = r * 2 - 2;
        for (int i = 0; i < r; ++i) { // 枚举矩阵的行
            for (int j = 0; j + i < n; j += t) { // 枚举每个周期的起始下标
                ans += s[j + i]; // 当前周期的第一个字符
                if (0 < i && i < r - 1 && j + t - i < n) {
                    ans += s[j + t - i]; // 当前周期的第二个字符
                }
            }
        }
        return ans;
    }
};