LeetCode の Decode String を Python 3 で解いてみた。

アルゴリズム

tl;dr スタックを使って与えられた文字列をパースしながら、出力文字列を組み立てた。具体的には次の通りである。

与えられた文字列を左から走査する。[ を発見するたび、そこまでに現れた数字とアルファベットをスタックにプッシュする。] を見つけたらスタックから値をふたつポップして (それぞれ prev_num と prev_str という名前と仮定する) cur_str = prev_str + cur_str * int(prev_num) として文字列を組み立てる。ここでの右辺の cur_str は現時点までに現れたアルファベットである。

時間計算量は O(n) と言ってよいはず。与えられた文字列を走査 (O(n)) しながら処理 (O(1)) をするため。

具体的なコードは次の通り。この実装で Runtime: 24 ms, faster than 84.71% of Python3 online submissions for Decode String. とのこと。

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# Difficulty: Medium
# https://leetcode.com/problems/decode-string/


class Solution:
    def decodeString(self, string: str) -> str:
        stack = []
        cur_num = ''
        cur_str = ''
        for char in string:

            # 入力文字は '[', ']', 数字, アルファベットの 4 パターンに分けて考える
            if char == '[':
                stack.append(cur_num)
                stack.append(cur_str)

                cur_num = ''
                cur_str = ''
            elif char == ']':
                prev_str = stack.pop()
                prev_num = stack.pop()

                cur_str = prev_str + cur_str * int(prev_num)
            elif char.isdecimal():
                cur_num += char
            elif char.isalnum():
                cur_str += char
            else:
                raise Exception('Should not come here')

        return cur_str


s = Solution()
print(s.decodeString('3[a]2[bc]'))  # Expected: "aaabcbc"
print(s.decodeString('3[a2[c]]'))  # Expected: "accaccacc"
print(s.decodeString('2[abc]3[cd]ef'))  # Expected: "abcabccdcdcdef"