ゼロから始めるLeetCode Day41「394. Decode String」

概要

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

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

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

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

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

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day40「114. Flatten Binary Tree to Linked List」
次回
ゼロから始めるLeetCode Day42「2. Add Two Numbers」

Twitterやってます。

問題

394. Decode String

問題としては、エンコードされた文字列を指定すると、そのデコードされた文字列を返すようなアルゴリズムを設計しましょう、というものです。

エンコーディングルールは、k[encoded_string]です。角かっこ内のencoding_stringは、正確にk回繰り返されます。 kは正の整数であることが保証されていることに注意してください。

入力文字列は常に有効であると想定できます。余分な空白はなく、角括弧は整形式などです。

さらに、元のデータに数字が含まれておらず、数字はこれらの繰り返し番号kのみに対応していると想定することもできます。たとえば、3aや2[4]のような入力はありません。

例としては以下の通りです。

s = "3[a]2[bc]", return "aaabcbc". s = "3[a2[c]]", return "accaccacc". s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

解法

class Solution:
    def decodeString(self, s: str) -> str:
        stack,curNum,curStr = [],0,''
        for st in s:
            if st == "[":
                stack.append(curStr)
                stack.append(curNum)
                curStr = ""
                curNum = 0
            elif st == "]":
                num = stack.pop()
                preStr = stack.pop()
                curStr = preStr + num*curStr
            elif st.isdigit():
                curNum = curNum*10 + int(st)
            else:
                curStr += st
        return curStr
# Runtime: 20 ms, faster than 98.29% of Python3 online submissions for Decode String.
# Memory Usage: 13.9 MB, less than 5.77% of Python3 online submissions for Decode String.                

stackを用いて解きました。
for文で最初から要素を舐めていき、与えられた要素によって処理を変えました。
たまたまとはいえ速いですね・・・

良い感じなので今回はここまで！お疲れ様でした。