[leetcode-6] Zigzag Conversion

LeetCode-6

Zigzag Conversion : The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows

note : like this: (you may want to display this pattern in a fixed font for better legibility)

Answer

        :::python

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows==1:
            return s
        answer = ''
        interval = numRows + (numRows-2)
        ls = [[''] for _ in range(numRows)] 
        for i, l in enumerate(s):
            inter = i%interval
            if inter < numRows:
                ls[inter]+=l
            else:
                ls[interval-(inter)]+=l
        return ''.join(sum(ls,[]))

Result : 97ms Memory: 14.2mb

Zigzag Conversion

Zigzag Conversion은 문자열을 지그재그 형태로 변환하는 알고리즘입니다.

문제 설명

주어진 문자열 s와 정수 numRows가 주어지면, s를 지그재그 형태로 변환합니다.

예를 들어, 다음과 같은 문자열과 numRows가 주어졌다고 가정해봅시다.

s = "PAYPALISHIRING"
numRows = 3

그러면 문자열 s는 다음과 같이 변환됩니다.

P   A   H   N
A P L S I I G
Y   I   R

즉, numRows개의 행으로 구성된 표에 문자열 s를 적절하게 배치하여 위와 같은 모양을 만듭니다.

해결 방법

Zigzag Conversion 문제를 해결하기 위해서는 다음과 같은 알고리즘을 사용할 수 있습니다.

1. numRows개의 빈 문자열 생성

2. 문자열 s를 처음부터 끝까지 순회하면서 다음과 같은 과정을 반복합니다.

   1. 현재 문자를 row번째 행에 추가합니다.

   2. row값이 0이거나 numRows - 1이면 방향을 전환합니다.

   3. 현재 방향에 따라 row값을 증가하거나 감소합니다.

3. 생성된 numRows개의 문자열을 순서대로 이어붙인 결과를 반환합니다.

예를 들어, 앞서 나온 예제를 위의 알고리즘으로 해결해보면 다음과 같습니다.

s = "PAYPALISHIRING"
numRows = 3

초기 상태:
["", "", ""]

s[0] = "P" 추가:
["P", "", ""]

s[1] = "A" 추가:
["P", "A", ""]

s[2] = "Y" 추가:
["P", "A", "Y"]

방향 전환:
["P", "A", "Y"]
["", "L", ""]

s[3] = "P" 추가:
["P", "A", "Y"]
["", "L", "P"]

s[4] = "A" 추가:
["P", "A", "Y"]
["", "L", "PA"]

s[5] = "L" 추가:
["P", "A", "Y"]
["", "L", "PAL"]

s[6] = "I" 추가:
["P", "A", "Y"]
["I", "L", "PAL"]

s[7] = "S" 추가:
["P", "A", "Y"]
["I", "LS", "PAL"]

s[8] = "H" 추가:
["P", "A", "Y"]
["I", "LSH", "PAL"]

s[9] = "I" 추가:
["P", "A", "Y"]
["IH", "LSH", "PAL"]

s[10] = "R" 추가:
["P", "A", "Y"]
["IH", "LSHR", "PAL"]

최종 결과: "PAHNAPLSIIGYIR"