Problem: 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".

Solution: ZigZag Conversion, Python:

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
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# @Date : 2015-02-06 21:21:05
# @Author : NSSimacer
# @Version : 1.0
class Solution:
# @return a string
def convert(self, s, nRows):
if nRows == 1:
return s
result = [''] * nRows
index = 0
step = 1
for i in xrange(len(s)):
result[index] += s[i]
# 到达最底下一行,步进-1,递减,开始向上
if index == nRows - 1:
step = -1
# 到达最顶上一行,步进1,递增,开始向下
if index == 0:
step = 1
index += step
return ''.join(result)

直观解法,找数学规律可能比较费时。时间复杂度 O(N),空间复杂度 O(1)。