6. Z 字形变换 | LeetCode算法题解

题目描述

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

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例：

略。

来源： Leetcode

思路

这题容易想到使用二维数组模拟字符排列，再依次按行读取的办法。

其实还有更简便的解法。

结果需要按行排列的结果，我们只需要把字符按行分好，再合并即可。纵向来看，字符一直是从上到下、再从下到上往返分配给每一行。所以我们记住方向和当前行，不断迭代分配字符，最后再合并到一起就得到了结果。

解法

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
const convert = (s, numRows) => {
  if (numRows === 1 || s.length <= numRows) return s;

  const rows = new Array(numRows).fill('');

  let curRow = 0;
  let goingDown = false;

  for (let c of s) {
    rows[curRow] += c;

    if (curRow === 0 || curRow === numRows - 1) {
      goingDown = !goingDown;
    }

    curRow += goingDown ? 1 : -1;
  }

  return rows.join('');
};