[leetcode algorithms]題目6

6. ZigZag Conversion

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 NA P L S I I GY 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".

自己寫的代碼：

定義next函數，讓字元的位置上下波動，遇到邊界則返回。定義numRows個列表，遍歷字元，把字元賦值給對應的列表，移動字元的「坐標」，最後合併列表。運行時間209 ms

class Solution: def next(self, i, numRows, direction): if numRows == 1: pass else: i = i + direction if i == -1 or i == numRows: direction = -direction i += direction * 2 return i, direction def convert(self, s, numRows): res = [[] for _ in range(numRows)] i = 0 direction = 1 for char in s: res[i].append(char) i, direction = self.next(i, numRows, direction) return .join([.join(x) for x in res])

討論區的優秀代碼：思路幾乎一樣，但是人家寫得更簡潔

class Solution: def convert(self, s, numRows): step = (numRows == 1) - 1 # 0 or -1 rows, idx = [] * numRows, 0 for c in s: rows[idx] += c if idx == 0 or idx == numRows-1: step = -step # change direction idx += step return .join(rows)

推薦閱讀：