[Python-Leetcode] 6. Zigzag Conversion (difficulty : Medium- ☆☆)

문제 설명

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

Example 3:

Input: s = "A", numRows = 1
Output: "A"

 

Constraints:

• 1 <= s.length <= 1000
• s consists of English letters (lower-case and upper-case), ',' and '.'.
• 1 <= numRows <= 1000

 

 

문제 풀이

1) 처음 도전

너무 시간이 너무 오래걸리네요

class Solution(object):
    def convert(self, s, numRows):
        
        leng = len(s)

        if numRows == 1:
            return s

        lists = [['' for i in range(leng)] for j in range(numRows)]

        ans = ''
        rows = columns = _cnt =  0

        for idx in range(leng):
            
            # down case
            if columns % (numRows-1)==0:
                #print('case1', s[idx], rows, columns)
                lists[rows][columns] = s[idx]
                rows +=1
                _cnt +=1
            
            # triangle up case
            elif columns % (numRows-1) !=0:
                #print('case2', s[idx], rows, columns)
                lists[rows][columns] = s[idx]
                columns +=1
                rows -= 1
                
            
            if _cnt == (numRows):
                rows-=2
                columns+=1
                _cnt=0

        for i in range(numRows):
            for s in lists[i]:
                if s!='':
                    ans+=s
        
        return ans

 

2) 다른 방법

0번째 열, 1번째 열, 2번째 열..에 각 문자를 순서대로 넣어서 return

class Solution:
    def convert(self, s, numRows):
        if numRows == 1: 
            return s
        
        store = [[] for _ in range(numRows)] 
        res = ''
        downflag = True
        idx = 0

        for i in s:
            store[idx].append(i)

            if idx == 0:
                downflag = True
            elif idx == (numRows-1):
                downflag = False # upflag
            
            if downflag:
                idx+=1
            else:
                idx-=1

        for i in list(map(''.join, store)):
            res+=i
        
        return res