将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

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

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”PAHNAPLSIIGYIR”。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);

示例1：

输入：s = “PAYPALISHIRING”, numRows = 3 输出：“PAHNAPLSIIGYIR”

示例2：

输入：s = “PAYPALISHIRING”, numRows = 4 输出：“PINALSIGYAHRPI”

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

示例3：

输入：s = “A”, numRows = 1 输出：“A”

提示：

  • 1 <= s.length <= 1000
  • s 由英文字母（小写和大写）、’,’ 和 ‘.’ 组成
  • 1 <= numRows <= 1000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/zigzag-conversion
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二维矩阵

变换周期：t = numRows + numRows - 2
周期列：tc = 1 + numRows - 2
时间复杂度：O(rn)，r = numRows, n = s.length
空间复杂度：O(rn)

  1. function convert(s: string, numRows: number): string {
  2.     const len = s.length;
  3.     if (numRows === 1 || numRows >= len) {
  4.         return s;
  5.     }
  6.     const term = 2 * numRows - 2;
  7.     const numColumns = Math.floor(len/term * (numRows - 1));
  8.     const array: Array<Array<string>> = new Array(numRows).fill('').map(() => new Array(numColumns).fill(''));
  9.     for (let i = 0, x = 0, y = 0; i < len; i++) {
  10.         array[x][y] = s.charAt(i);
  11.         if (i % term < numRows - 1) {    // 区分属于一个周期内的左侧竖列，还是右侧斜向上部分
  12.             x++;  
  13.         } else {
  14.             x--;
  15.             y++;
  16.         }
  17.     }
  18.     let newS = '';
  19.     for (const row of array) {
  20.         newS += row.filter(ch => ch !== '').join('');
  21.     }
  22.     return newS;
  23. };

压缩矩阵

上述方法的矩阵中存在空字符，若将二维矩阵变换为一维，则在时间和空间都将缩减其复杂度。
时间复杂度：O(n)
空间复杂度：O(n), 压缩后的矩阵需要 O(n)O(n) 的空间

function convert(s: string, numRows: number): string {
    const len = s.length;
    if (numRows === 1 || numRows >= len) {
        return s;
    }
    const term = 2 * numRows - 2;
    const array: Array<string> = new Array(numRows).fill('');
    for (let i = 0, x = 0; i < len; i++) {
        array[x] += s.charAt(i);
        if (i % term < numRows - 1) {    // 区分属于一个周期内的左侧竖列，还是右侧斜向上部分
            x++;  
        } else {
            x--;
        }
    }
    return array.join('');
};

直接构造

上述方法中无需矩阵，可以直接使用[] 或 newString 来实现。

function convert(s: string, numRows: number): string {
    const len = s.length;
    if (numRows === 1 || numRows >= len) {
        return s;
    }
    const term = 2 * numRows - 2;
    let newStr = '';
    for (let i = 0; i < numRows; i++) {    // 枚举Z图形中的行
        for (let j = 0; j < len - i; j+=term) {    // 枚举每个周期的起始位置
            newStr += s[i + j];    // 当前周期的第一个字符
            if (0 < i && i < numRows - 1 && j + term - i < len) {
                newStr += s[j + term - i];    // 当前周期的第二个字符  
            }
        }
    }
    return newStr;
};