6. Zigzag Conversion

source: https://leetcode.com/problems/zigzag-conversion/

Question

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);

暴力法

二维数组，逐个变换方向插入：

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    // 下，斜上
    const directions = [[1, 0], [-1, 1]];
    const ret = Array(numRows).fill(null).map(() => Array(s.length).fill(''));
    const dfs = (y, x, n, v) => {
        if (v >= s.length) return;
        const [offsetY, offsetX] = directions[n % directions.length];
        y += offsetY;
        x += offsetX;
        let crr = ret[y]?.[x];
        while (crr !== undefined) {
            ret[y][x] = s[v];
            v += 1;
            const nextY = y + offsetY;
            const nextX = x + offsetX;
            crr = ret[nextY]?.[nextX];
            if (crr !== undefined) {
                y = nextY;
                x = nextX;
            }
        }
        dfs(y, x, n + 1, v);
    };
    dfs(-1, 0, 0, 0);
    console.log(ret)
    return ret.map(row => row.join('')).join('');
};

变换Flga

在Z字形变换中，有一个规律：

• 不管现在在哪行，x轴总是+1
• 每次变换方向，y轴的变换方向都会逆转

由此可以用一个flag控制y轴的变换方向：

function convert(s: string, numRows: number): string {
    if (numRows < 2) return s;
    const ret = Array(numRows).fill('');
    let i = 0;
    let flag = -1;
    Array.from(s).forEach(c => {
        ret[i] += c;
        if (i === 0 || i === numRows - 1) {
            flag = -flag;
        }
        i += flag;
    });
    return ret.join('');
};

End

找到规律，往往能事半功倍。