Rail Fence Cipher

The rail fence cipher (also called a zigzag cipher) is a classical type of transposition cipher. The process is simple, we put data into a fence-like table with a special format and take them out with with another format, then we can make data encoded.

Below table I take from wiki shows how to put WE ARE DISCOVERED. RUN AT ONCE.' into a table.

W . . . E . . . C . . . R . . . U . . . O . . . 
. E . R . D . S . O . E . E . R . N . T . N . E 
. . A . . . I . . . V . . . D . . . A . . . C .

And then, we read data row by row to get an encoded data WECRUO ERDSOEERNTNE AIVDAC.

Now we understand its process, let's see how to code this.

The leetcode Zigzag Conversion is very similar to rail fence cipher, let's use it to see how to implement it in code.

Walk By Row

The idea of this method is to find the relation between the index from the row table and the index of characters.

Take string a-v as an example.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
a b c d e f g h i j k  l  m  n  o  p  q  r  s  t  u  v

0 a       i       q
1 b     h j     p r
2 c   g   k   o   s
3 d f     l n     t v
4 e       m       u

Suppose we try to iterate row by row the find the exact index of the character. Code logic like below.

let result = "";

for (let i = 0; i < numRows; i++) {
    const sIndex = x; // try to find index of string
    result += s[sIndex];
}

Ignore the inner pattern, try to consider below table first.

0 a       i       q
1 b       j       r
2 c       k       s
3 d       l       t
4 e       m       u

This seems a lot easy. For the first row, we know that we can get result aiq, which has index 0, 8, 16 in the string. For second row, we can get bjr with index in string as 1, 9, 17. For third row, we can get cks with index in string as 2, 10, 18. Can you see the pattern here? The cycle length is alway value 8, ex: 8-0, 16-8, 9-1.... This value is related with the number of rows and we can easily find the formula cycleLen = 2*numRows - 2.

OK, now let's consider the inner pattern.

0 a       i       q
1 b     h j     p r
2 c   g   k   o   s
3 d f     l n     t v
4 e       m       u

only inner part =>

0                  
1       h       p  
2     g       o    
3   f       n       v
4

First thing we can see here is that if the current row's index is equal to 0 or numRows-1, then there is no inner pattern. Second, take a look at the row with index 1, it has value bhjpr and inner value hp. We can see that character h just 1 step before next normal pattern value j. For row with index 2, it has value cgkos and inner value go. We can see that character g just 2 step before next normal pattern value k. So we find another formula j + cycleLen - curRowIndex, j is the value we found in normal pattern.

So with these 2 part, we can come up a solution.

function convert(s: string, numRows: number): string {
    if (numRows === 1) return s;

    let result: string[] = [];
    const cycleLen = 2 * numRows - 2;

    // i => rowIndex
    for (let i = 0; i < numRows; i++) {

        // j => start step
        let j = 0;
        while (true) {
            const si1 = j + i;
            if (si1 >= s.length) break;

            result.push(s[si1]);

            if (i !== 0 && i !== numRows - 1) {
                const si2 = j + cycleLen - i;
                if (si2 < s.length) {
                    result.push(s[si2]);
                }
            }

            j += cycleLen;
        }
    }

    return result.join("");
};

Walk By Character

This method is easier than the first one. We just init an array to simulate the row table. And when we iterate the string, we put characters into correct rows. At the end, we join them back together.

function convert(s: string, numRows: number): string {
    if (numRows === 1) return s;
    const rows = Array.from({ length: numRows }, _ => "");

    let curRow = 0;
    let goDown = false;

    for (const char of s) {
        rows[curRow] += char;

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

        if (goDown) {
            curRow += 1;
        } else {
            curRow -= 1;
        }
    }

    return rows.reduce((pre, cur) => pre + cur);
};