概要

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

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

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

Leetcode

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day40「114. Flatten Binary Tree to Linked List」

今はTop 100 Liked QuestionsのMediumを解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。

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文で最初から要素を舐めていき、与えられた要素によって処理を変えました。
たまたまとはいえ速いですね・・・

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

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

概要

問題

解法