Simple Solution in Python with O(n) complexity


  • 0
    Z

    1. Intuition
    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.

    2. Analysis
    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

      0_1521003543065_1f4ace46-bcb5-4f1b-8605-9b2a99531cef-image.png

    • If numRows = 4 or 5, we can get the following:

      0_1521003573650_6b284469-89f6-479f-8a85-9c355f052513-image.png

      0_1521003587346_b6c6c594-dfcc-41c6-a3cc-0ae7538b5098-image.png

    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.

    3. Python

    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
    

    4. Complexity:

    • Time complexity: O(n). n is the length of the original string.

    • Space complexity: O(n). The space is used to store the result.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.