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

問題
1. 原文
2. 内容
方針
1. 前提
2. 実装のイメージ
解答
1. 解答1：
2. 解答2：Python, 英語コメント付き
補足・参考・感想

問題

原文

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：Python, 英語コメント付き

"""
Question
I'm Given string and numRows. And I have to return converted string.
The conversion is that I repalace the characters in the string such like following.
pattern1: ABCDEFGHIJK, numRows=3
 A   E   I
 B D F H J
 C   G   K
the answer of pattern1 is "AEIBDFHJCGK"

Assumption
 -the string has no space.
 -the string has at least one character.
 -the string has only English letters and "," and ".".
 -the lentgh of string is less than 10^4(ten to the power of 4)
-If I come up with any other assumption, let me add it.

Testcase
 1.Regular case:"ABCDEFGHIJK"
 2.Regular case:"A"
 3.Edge case: "......."
 4.Edge case: "ABCDE", numRow=10

Approach
 1.Brute Force
  I initilize two dimensional array and perform double for loop.
  Outer loop iterate over rows and inner loop iterate over columns.
  each caharacter of "s" is inserted to current position in each loop.
"""


class Solution(object):
    def convert(self, s, numRows):
      if numRows==1 or numRows>=len(s):
        return s

      index = 0
      step = 1
      answer = [""]*numRows

      for i in s:
        answer[index] += i
        if index == numRows-1:
          step = -1
        elif index == 0:
          step = 1                
        index += step

      return ''.join(answer)

"""

Question

I'm Given string and numRows. And I have to return converted string.

The conversion is that I repalace the characters in the string such like following.

pattern1: ABCDEFGHIJK, numRows=3

A E I

B D F H J

C G K

the answer of pattern1 is "AEIBDFHJCGK"

Assumption

-the string has no space.

-the string has at least one character.

-the string has only English letters and "," and ".".

-the lentgh of string is less than 10^4(ten to the power of 4)

-If I come up with any other assumption, let me add it.

Testcase

1.Regular case:"ABCDEFGHIJK"

2.Regular case:"A"

3.Edge case: "......."

4.Edge case: "ABCDE", numRow=10

Approach

1.Brute Force

I initilize two dimensional array and perform double for loop.

Outer loop iterate over rows and inner loop iterate over columns.

each caharacter of "s" is inserted to current position in each loop.

"""

class Solution(object):

def convert(self, s, numRows):

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

return s

index = 0

step = 1

answer = [""]*numRows

for i in s:

answer[index] += i

if index == numRows-1:

step = -1

elif index == 0:

step = 1

index += step

return ''.join(answer)

解答1とコードは同じ

answer = [“”]*numRowsでnumRowsの値の数だけ要素を持つリストを作成できる。

こういう基本的なPythonの動作は忘れがちだから必ず復習しておきたい。

英語コメントは実際の面接をイメージしてまずはディスカッションの内容を書き出してみた。

内容についてコメントしてもらえる人に相談したい。

この内容をさらに精緻化して、その上でスムーズに会話できる必要がある。

その後で、コードを書きながら何をしているのかを説明できるようになる必要がある。

目標は遠いけど、1つ1つクリアしていく。

補足・参考・感想

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

参考

前：5. Longest Palindromic Substring

次：7. Reverse Integer

LeetCode 解答・解説記事一覧