[LeetCode] 006. 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   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);



Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"



Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I


解題邏輯與實作

基本上這題就是在找規律,有點麻煩的說…

用一個比較好說明的例子,在找規律的時候,我先觀察了直行的部份:

numRows(n) = 5

row0:  0     8         16       24
row1:  1   7 9      15 17     23
row2:  2  6  10   14   18   22
row3:  3 5   11 13     19 21
row4:  4     12        20 



取出各個row,直行的部份,會發現它們都是等差數列,其差值可表示為2(n1)2\ast(n-1)

row0:  0, 8,  16
row1:  1, 9,  17
row2:  2, 10, 18
row3:  3, 11, 19
row4:  4, 12, 20 



另外可以發現,除了第一列與最後一列(row = 0 與 n-1)外,其他列在兩個直行之間會在多輸出一個字元,將著個字元與前一個字元合併用pair表示,每一個pair都是一個等差,其差值可表示為2(n1i)2\ast(n-1-i), 其中i=0,...n1i = 0, ... n-1

row1:  (1,7), (9,15),  (17,23)
row2:  (2,6), (10,14), (18,22)
row3:  (3,5), (11,13), (19,21)



此外,需要稍微注意一下corner case,為了簡單起見,我將numRows小於等於1,以及numRows大於等於s的長度的case,做了特別判斷,直接將輸入的s回傳回去。


程式碼

class Solution:
	def convert(self, s, numRows):
		if numRows<=1 or numRows >= len(s):
			return s

		result = ""
		
		len_s = len(s)
		max_row_number = numRows-1
		skip_mid_check = False
		for i in range(numRows):
			skip_mid_check = i == 0 or i == numRows-1
			for n in range(i,len_s, 2 * max_row_number):
				result += s[n]
				if not skip_mid_check:
					next_idx = n + 2 * (max_row_number-i)
					if next_idx < len_s:
						result += s[next_idx]
		return result



[LeetCode] 解題目錄 -> 這裡走

留言

這個網誌中的熱門文章

Genymotion 模擬器安裝篇:In ubuntu14.04 LET