A string in a ZigZag pattern has a regularity in it. If we can find out what the regularity is and then take advantage of it, this problem would be very simple to handle.
Let's take the string in the description as an example. Now we get the string s = 'PAYPALISHIRING' and numRows = 3. The s will be rearranged as shown below:
numRows = 3
If numRows = 4 or 5, we can get the following:
From the figures it can be seen that if we divide the string into several groups in imaginary line like above, each group will have the same length. And each character in each line is related to this length. So we can rearrange the string with this relations to get the final result.
From the analysis above, if we get a specific numRows, the total length of each group of the string totalLens = 2 * numRows - 2. By knowing that, we can get the number of the total groups groupNums = len(s) // totalLens.
Hold on. If the len(s) cannot be exactly divided by totalLens, the number of characters in the last group will be less than the totalLens. The number of groups will also become len(s) // totalLens + 1. To avoid splitting the problem in different situations, we can add some specific characters like '#' into the end of the original string, to make it be divided exactly by totalLens. Before returning the final result we can remove all the specific characters in the string.
In addition, from the figures above, we can find out that in each group, there is only 1 character in the first and last line, and exactly 2 characters in each intermediate line. So we can handle the first and last line separately in a loop and all the intermediate lines in one loop.
Everything is okay now. Coding starts.
class Solution: def convert(self, s, numRows): """ :type s: str :type numRows: int :rtype: str """ # If the numRows == 1, the result equals to the original string if numRows == 1: return s # Get total length totalLens = 2 * numRows - 2 # Add specific characters into the end of the string lpad = len(s) % totalLens if lpad != 0: s += '#' * (totalLens - lpad) # Get the number of groups resultRow = len(s) // totalLens resultStr = '' # i & j are used to control the index of each characters in the intermediate lines i, j = 1, totalLens - 1 # Firstly get each characters in the first line for k in range(resultRow): resultStr += s[k * totalLens] # Get all the intermediate lines while i < j: for k in range(resultRow): resultStr += s[k * totalLens + i] resultStr += s[k * totalLens + j] i += 1 j -= 1 # Get each characters in the last line for k in range(resultRow): resultStr += s[k * totalLens + totalLens // 2] # Remove the specific character from the result resultStr = resultStr.replace('#', '') return resultStr
Time complexity: O(n). n is the length of the original string.
Space complexity: O(n). The space is used to store the result.