【スナップ】394:文字列復号|スタック|再帰

久しぶりに更新して、今日は科目2を試験して、やっと勉強を続ける時間がありました.
タイトルの説明
符号化された文字列を指定し、復号された文字列を返します.
符号化規則は、四角カッコ内部のk[encoded_string]がちょうどk回繰り返されることを示すencoded_stringである.注意kは正の整数であることを保証する.
入力文字列は常に有効であると考えられます.入力文字列には余分なスペースがなく、入力した四角カッコは常にフォーマットの要件を満たしています.
また、元のデータには数字は含まれておらず、すべての数字は重複回数kのみを表し、例えば3 aや2[4]のような入力は現れないと考えられます.

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

ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/decode-string著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
アルゴリズムの考え方
1回目の読解では「わあ、簡単だね.分を分けて書いてあげる」と思っていましたが、落ち着いてみると、思ったほど簡単ではありませんでした.
そして最初に思いついたのはセグメントで、[]内の部分を再帰的に解いて、ガチョウ......直接アルゴリズムを見ましょう.

class Solution:
    def decodeString(self, s: str) -> str:
        res=''
        i=0
        while i<len(s):
            if s[i].isalpha():
                res+=s[i]
                i+=1
            else:
                b=i
                left=s.find('[',i)
                if left==-1:
                    res+=s[i:]
                    break
                i=left
                right=s.find(']',i)
                res+=eval(s[b:left])*self.decodeString(s[left+1:right])
                i=right+1
        return res

しかし、この頭にすぎないアルゴリズムはs = "3[a2[c]]",も解決できない......
そしてラベルを一目見て、【桟】?正直に心を静めて分析してみると、[に出会ったら、それまでの数字の部分をスタックに入れて、残りの部分はどうしますか.再帰.再帰の終了条件は何ですか?明らかに]が戻ってきた.このとき出会った問題は......ポインタiが再帰終了後にどのように更新されるかということです.不完全なコードは次のとおりです.

    def decodeString(self, s: str) -> str:
        res,num,i,ls='','',0,[]

        while i<len(s):
            if s[i].isalpha():
                res+=s[i]
            elif s[i].isdigit():
                num+=s[i]
            elif s[i]=='[':
                ls.append(int(num))
                num=''
                i+=1
                res+=ls.pop()*self.decodeString(s[i:])
            elif s[i]==']':
                return res
            i+=1

そしてふと思うと、iを更新するとポインタiが一方の文字列sだけを完全に通過したことを意味するので、ポインタiをより高度な変数空間で保存すればいいのではないでしょうか.完全なアルゴリズム

class Solution:
    def __init__(self):
        self.i=0

    def decodeString(self, s: str) -> str:
        res=''
        num=''
        ls=[]
        while self.i<len(s):
            if s[self.i].isalpha():
                res+=s[self.i]
            elif s[self.i].isdigit():
                num+=s[self.i]
            elif s[self.i]=='[':
                ls.append(int(num))
                num=''
                self.i+=1
                res+=ls.pop()*self.decodeString(s)
            elif s[self.i]==']':
                return res
            self.i+=1
        return res

実行時間:36 ms、すべてのPython 3コミットで82.08%のユーザーメモリ消費量:13.6 MBを破り、すべてのPython 3コミットで20.00%のユーザーを破った
――というか、反省日記は有効だったのですが、このブログを書いているうちに、そんなスタックスペースを追加する必要はないような気がしてきました

class Solution:
    def __init__(self):
        self.i=0

    def decodeString(self, s: str) -> str:
        res=''
        num=''
        while self.i<len(s):
            if s[self.i].isalpha():
                res+=s[self.i]
            elif s[self.i].isdigit():
                num+=s[self.i]
            elif s[self.i]=='[':
                self.i+=1
                res+=int(num)*self.decodeString(s)
                num=''
            elif s[self.i]==']':
                return res
            self.i+=1
        return res

実行時間:24 ms、すべてのPython 3コミットで99.64%のユーザーメモリ消費量:13.8 MBを破り、すべてのPython 3コミットで20.00%のユーザーを破った