【LeetCode学習記録】ZigZag Conversionを解いた

今日は，ZigZag Conversionを解きました．その中で学んだことを記録しておきます．
なお，私はPython初心者かつ，LeetCodeのような問題も始めたばかりなので，間違いの指摘や，アドバイスなどがあればお待ちしております．

#問題設定
s="PAYPALISHIRING"という文字列に対し，numRows=3が与えられたとき，

result

P A H N
APLSIIG
Y I R

のようにギザギザになる．outputは各行を左から順に並べた"PAHNAPLSIIGYIR"となる．

最初に書いたコード

方針

• 与えられた文字列sについて，先頭から順に0,1,...,(numRows-1),(numRows-2),...,1,0,...のようにkey=0,1,...,numRows-1を割り当てる．
  • インクリメント/デクリメントを判断する識別子Incが必要？
• keyの小さいほうから順に結合し，それをoutputとして返す．
  • どうすれば文字列を結合できる？

以上の方針から，次のようなコードを書いた：

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        #エッジケースの処理
        if(numRows <= 1):
            return s
        
        d = defaultdict(list)
        Inc = True
        key = 0
        # label 0, 1,2,...,numRows,numrows-1,...,1,0,...
        for i in range(len(s)):
            d[key].append(s[i])
            if(key == numRows - 1):
                Inc = False
            elif(key == 0):
                Inc = True
            if(Inc == True):
                key += 1
            else:
                key -= 1
                
        # join d
        ans = ''
        for i in range(numRows):
            ans += ''.join(d[i])
        return ans

Runtime: 64ms
Memory: 12.8MB

つまづいた点

同一のkeyを持つ要素の格納方法

同一のkeyを持つs[i]に対して，

d[key] = s[i]

とすると，値が上書きされてしまった．
これは，リストのメソッドappend()を用いて，末尾に要素を追加するようにして解決した．
リスト関係のメソッドは他にも将来使いそうなものがたくさんあるので，今後勉強していきます．

リストを文字列に変換する方法

forループ直後のdは，

{0: [u'P', u'A', u'H', u'N'], 
1: [u'A', u'P', u'L', u'S', u'I', u'I', u'G'], 
2: [u'Y', u'I', u'R']}

のようになっていた．
forループを使って結合していくのも面倒だなと思って著と調べてみたら，リストを文字列に変換してくれるjoin()メソッドを見つけた．例えば，

d[0] = ['P','A','H','N']
'.'.join(d[0]) # => 'P.A.H.N'

のようになる．
今回は''内に何も入れなければ単純に連結することになる．
そして，joinした文字列をkeyの小さい順にansへ足しこんでいけば，所望のoutputが得られる．

コードの改善

LeetCodeでは，他人の考えたコードを見れる「Discuss」がとても良い．
この問題ではこちらを参考にさせてもらった．
改善版のコードは次に示す：

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if(numRows <= 1):
            return s        
        
        d = [""] * numRows
        Inc = True
        key = 0

        for i in range(len(s)):
            d[key] += s[i]
            if(key == numRows - 1):
                Inc = False
            elif(key == 0):
                Inc = True
            if(Inc == True):
                key += 1
            else:
                key -= 1
                
        
        return ''.join(d)

Runtime: 28ms(<= 64ms)
Memory:12.7MB(<=12.7MB)
で，実行時間を1/2以下にすることができた．

リスト配列の初期化

例えば，

L = ['','','']

といったリスト配列を作るとき，

L = [''] * 3

とすれば，上と同等のものが出来ることを知った．
今回は0~numRows-1までのnumRowsこの要素が必要であることが明らかであるため，こちらのほうが柔軟かつ明示的になるだろう．

keyごとの分類の改善

今思えば，同一のkeyの場合はappend()するよりも，最初から結合したほうが1つ手順が減らせることに気づいた．
このようにすることで，forループ後にもう一度forループを用いて文字列を結合せずに，''.join()のみで済む．