ZigZag Conversion

Description

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 text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

输入之字字符串和之字的行数,要求按行输出字符串。

"A-Z"5行的之字字符:

   0 1 2 3 4 5 6 7 8 ...

0  A       I       Q       Y
1  B     H J     P R     X Z
2  C   G   K   O   S   W
3  D F     L N     T V
4  E       M       U

可以看出:

  1. 第0、第4、第8、第12列每行都有字符,其他列只有一个字符 col % (5 - 1) == 0
  2. 其他列字符所在行: row = (5 - 1) - (col % (5 - 1))
  3. 字符在输入字符串中的位置(0起)等于: index = col * 2 + row

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
func convert(s string, numRows int) string {
    /*       0  1  2  3  4  5  6    col
     *     +----------------------
     *  0  | 0  x  x  6  x  x  12
     *  1  | 1  x  5  7  x 11
     *  2  | 2  4  x  8 10
     *  3  | 3  x  x  9
     * row +----------------------
     *
     * col0: each line have a char
     * col1: the char is at row2
     * col2: the char is at row1
     *  .
     * col4: the char is at row2
     *
     * the char is at row( 4 - (col % 3) ) except col0、col0+3、col0+3+3...
     */

    if numRows == 1 {
        return s
    }

    var res string

    for row := 0; row < numRows; row++ {
        for col := 0; ; col++ {
            m := col % (numRows - 1)

            // if m == 0 there must be a char
            // else numRows-m eq the char' row-index
            if m == 0 || row == (numRows - 1) - m{
                idx := (col << 1) + row

                if idx >= len(s) {
                    break
                }

                res += string(s[idx])
            }
        }
    }

    return res
}