首页 > itarticle > zigzag conversion – leetcode a6

zigzag conversion – leetcode a6

admin 11月 12, 2020 0

Problem

Problem 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)

1
2
3

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:

1	string (string text, int nRows);

convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

Analysis

n = number of raws
For first and last line, step = 2n-2
For ith lines (except the first and the last), step = 2n-2-2*i, 2n-2

Python Implementation

class Solution:
    def (self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        
        if (numRows == 1):
        	return s
        step = numRows * 2 - 2
        ans = ""
        for i in range(numRows):
        	index = i
        	step2 = step - i * 2
        	if (index >= len(s)):
        		break
        	ans += s[index]
        	while (1):
        		if (step2 != 0 and step2 != step):
        			if (index + step2 >= len(s)):
        				break
        			ans += s[index + step2]
        		
        		index += step
        		if (index >= len(s)):
        			break
        		ans += s[index]        		
        return ans