[Leet Code learning record] Solved ZigZag Conversion

Today, I solved ZigZag Conversion. Make a note of what you learned in it. I'm new to Python and have just started problems like LetCode, so I'd love to hear any mistakes or advice.

Problem setting

When numRows = 3 is given to the string s = "PAYPALISHIRING"

result

P A H N
APLSIIG
Y I R

It becomes jagged like. The output is "PAHNAPLSIIGYIR" in which each line is arranged in order from the left.

The code I wrote first

policy

--For the given character string s, key = like 0,1, ..., (numRows-1), (numRows-2), ..., 1,0, ... from the beginning. Allocate 0,1, ..., numRows-1. --Need the identifier ʻInc` to determine increment / decrement? --Combines in ascending order of key and returns it as output. ――How can I combine strings?

Based on the above policy, I wrote the following code:

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        #Edge case handling
        if(numRows <= 1):
            return s
        
        d = defaultdict(list)
        Inc = True
        key = 0
        # label 0, 1,2,...,numRows,numrows-1,...,1,0,...
        for i in range(len(s)):
            d[key].append(s[i])
            if(key == numRows - 1):
                Inc = False
            elif(key == 0):
                Inc = True
            if(Inc == True):
                key += 1
            else:
                key -= 1
                
        # join d
        ans = ''
        for i in range(numRows):
            ans += ''.join(d[i])
        return ans

Runtime: 64ms Memory: 12.8MB

Stumble point

How to store elements with the same key

For s [i] with the same key,

d[key] = s[i]

Then, the value was overwritten. This was solved by using the list method ʻappend ()` and adding an element to the end. There are many other list-related methods that I might use in the future, so I will study them in the future.

How to convert a list to a string

The d immediately after the for loop is

{0: [u'P', u'A', u'H', u'N'], 
1: [u'A', u'P', u'L', u'S', u'I', u'I', u'G'], 
2: [u'Y', u'I', u'R']}

It was like this. I thought it would be a hassle to join using a for loop, so I looked it up and found a join () method that converts the list to a string. For example

d[0] = ['P','A','H','N']
'.'.join(d[0]) # => 'P.A.H.N'

become that way. This time, if nothing is put in '', it will be simply connected. Then, if you add the join string to ʻans in ascending order of key, you can get the desired ʻoutput.

Code improvements

In LeetCode, "Discuss" that allows you to see the code that others have thought of is very good. For this problem, I referred to here. The improved code is shown below:

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if(numRows <= 1):
            return s        
        
        d = [""] * numRows
        Inc = True
        key = 0

        for i in range(len(s)):
            d[key] += s[i]
            if(key == numRows - 1):
                Inc = False
            elif(key == 0):
                Inc = True
            if(Inc == True):
                key += 1
            else:
                key -= 1
                
        
        return ''.join(d)

Runtime: 28ms(<= 64ms) Memory:12.7MB(<=12.7MB) So, the execution time could be reduced to 1/2 or less.

List array initialization

For example

L = ['','','']

When creating a list array such as

L = [''] * 3

If so, I learned that the same thing as above can be made. This time numRows from 0 to numRows-1 It is clear that this element is needed, so this will be more flexible and explicit.

Improvement of classification by key

When I think about it now, I noticed that in the case of the same key, one step can be reduced by combining from the beginning rather than by ʻappend (). By doing this, you can just use ''. Join ()` without joining the strings again using the for loop after the for loop.