leetcode-394. 文字列復号

4456 ワード

タイトル


符号化された文字列を指定し、復号された文字列を返します.
符号化規則は、k[encoded_string]であり、カッコ内のencoded_を表すstringはちょうどk回繰り返します.注意kは正の整数であることを保証する.
入力文字列は常に有効であると考えられます.入力文字列には余分なスペースがなく、入力した四角カッコは常にフォーマットの要件を満たしています.
また、元のデータには数字は含まれておらず、すべての数字は重複回数kのみを表し、例えば3 aや2[4]のような入力は現れないと考えられます.
例1:
 :s = "3[a]2[bc]"
 :"aaabcbc"

例2:
 :s = "3[a2[c]]"
 :"accaccacc"

例3:
 :s = "2[abc]3[cd]ef"
 :"abcabccdcdcdef"

例4:
 :s = "abc3[cd]xyz"
 :"abccdcdcdxyz"

問題を解く構想.


最初はまだ何の考えもなかったが,後で問題解を見て思いついた.
1つのスタックで現在遭遇している文字の状況を保存し、数字であれば記録し、[であれば数字をスタックに入れ、アルファベットであればスタックに入れ、]であればスタックから最も右の数字の右のすべてのアルファベットを取り出し、最も右の数字とこれらのアルファベットを乗算して繰り返した文字列を得る.

コード#コード#

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        op = 0
        for ch in s:
            if ch == ']':
                cur_str = ''
                while type(stack[-1]) == str:
                    cur_str = stack.pop() + cur_str
                stack[-1] *= cur_str
            elif ch.isdecimal():
                op = op * 10 + int(ch)
            elif ch == '[':
                stack.append(op)
                op = 0
            else:
                stack.append(ch)                
        return ''.join(stack)