【LeetCode】6. Zigzag Conversion 解答・解説【Python】

問題
1. 原文
2. 内容
方針
1. 前提
2. 実装のイメージ
解答
1. 解答1：
2. 解答2
補足・参考・感想

問題

原文

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

1
2
3

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);

1

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"

1
2

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

1
2
3
4
5
6
7

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"

1
2

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

内容

文字列 “PAYPALISHIRING “は、次のように所定の行数にジグザグに書かれています（読みやすくするために、このパターンを固定フォントで表示するとよいでしょう）。

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

P A H N

A P L S I I G

Y I R

そして、1行ずつ読みます。→"PAHNAPLSIIGYIR"

※(example1のOutputと同じ)

文字列を受け取り、行数を指定してこの変換を行うコードを書いてください。

string convert(string s, int numRows);

1	string convert(string s, int numRows);

※正しくない可能性があります。

方針

前提

・解答例を見るとnumRows=3なのに3行だったり、1行だったりで悩む。各exampleのOutputだけを見た方が良いと思う。

・ジグザグに変換するというのは、numRowsの数だけ箱を作り、その各箱に対して左→右、右→左と順に文字列s内の各文字を追加していくイメージ。

実装のイメージ

解答

解答1：

class Solution(object):
    def convert(self, s, numRows):
        if numRows == 1 or numRows >= len(s):
            return s
        #LにはnumRowsの数だけ要素がある。Lの各要素に、文字列sの各要素を格納する。
        #ジグザグにするとは、Lの要素を左端から右端、もしくは右端から左端に往復するように移動し、
        #文字列sの各要素をLの各要素に追加すること
        L = [''] * numRows
        #indexはLの要素、stepは進行方向(左端から右端、右端から左端)を指す
        index, step = 0, 1
        
        #文字列sの各要素を順に処理
        for x in s:
            #Lの最初の要素に、文字列sの要素を追加
            L[index] += x
            #print(L)
            #print(index,"index")

            #indexが0、つまりLの左端ならstepを+1にする
            if index == 0:
                step = 1

            ##indexがnumRow-1、つまりLの右端ならstepを-1にする
            elif index == numRows -1:
                step = -1
            
            #indexに+1、-1のどちらかを加える
            #この操作により、左右どちらかの両端に到達するまでは一方向に進む
            index += step
        
        #Lの各要素を1つに結合して返す
        return ''.join(L)

class Solution(object):

def convert(self, s, numRows):

if numRows == 1 or numRows >= len(s):

return s

#LにはnumRowsの数だけ要素がある。Lの各要素に、文字列sの各要素を格納する。

#ジグザグにするとは、Lの要素を左端から右端、もしくは右端から左端に往復するように移動し、

#文字列sの各要素をLの各要素に追加すること

L = [''] * numRows

#indexはLの要素、stepは進行方向(左端から右端、右端から左端)を指す

index, step = 0, 1

#文字列sの各要素を順に処理

for x in s:

#Lの最初の要素に、文字列sの要素を追加

L[index] += x

#print(L)

#print(index,"index")

#indexが0、つまりLの左端ならstepを+1にする

if index == 0:

step = 1

##indexがnumRow-1、つまりLの右端ならstepを-1にする

elif index == numRows -1:

step = -1

#indexに+1、-1のどちらかを加える

#この操作により、左右どちらかの両端に到達するまでは一方向に進む

index += step

#Lの各要素を1つに結合して返す

return ''.join(L)

解答2

補足・参考・感想

サンプルを見ても何をすれば良いのか理解できず困ってしまった。

参考

前：5. Longest Palindromic Substring

次：7. Reverse Integer

LeetCode 解答・解説記事一覧