ゼロから始めるLeetCode Day85 「6. ZigZag Conversion」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day84「142. Linked List Cycle Ⅱ」

次回
ゼロから始めるLeetCode Day86 「33. Search in Rotated Sorted Array」

Twitterやってます。

問題

6. ZigZag Conversion

難易度はMedium。
前回に引き続き、コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、まず、文字列、例えばPAYPALISHIRINGという文字列が与えられます。それらの文字列は以下のように所定の行数にジグザグパターンで書かれています。(読みやすくするために、このパターンを固定フォントで表示するとよいでしょう)

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

これらを一行ずつ読んでいくと "PAHNAPLSIIGYIR"となります。

これらの文字列を受け取り、行数を指定して変換するコードを書きます。

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

そういえば問題集のリストをクローンしたのですが、僕が解いた問題は今の時点で23/60でした。

こんな感じ↓

楽しく解くことを大事にしているので無理しない範囲で全部回答していきたいですね。
あ、あと地味にサブスクライブしないと解けない問題があったりします。
それはそもそも僕がサブスクライブしていても問題を載せることは権利的にどうなんだってことでスキップさせてもらいます。

#解法

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s
        num,step,ans = 0,0,['']*numRows
        for w in s:
            ans[num] += w
            if num == 0:
                step = 1
            elif num == numRows - 1:
                step = -1
            num += step
        return "".join(ans)
# Runtime: 64 ms, faster than 65.13% of Python3 online submissions for ZigZag Conversion.
# Memory Usage: 14.1 MB, less than 10.13% of Python3 online submissions for ZigZag Conversion.

numRowsの数の分だけ配列を用意してそれぞれ追加していきます。追加した後にstepで増減を管理することで、例えばテストケースの

PAYPALISHIRING

場合は以下のように配列に挿入できていることが分かります。

['PAHN', 'APLSIIG', 'YIR']

これを最終的に''で``join()してあげれば無事にstrの“PAHNAPLSIIGYIR”`が返される、といった具合です。

これで24/60ですね。
では今回はここまで。お疲れ様でした。