leetcode394.文字列復号『華為2019秋の搭乗問題』

1923 ワード

1.タイトルの説明


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

2.問題の解き方


一時結果変数resを格納するように設定します.文字列の先頭文字は「[」ではなく、アルファベットではなく数字です.アルファベットに遭遇した場合はresに保存し、数字に遭遇した場合はkに保存します.「[」に遭遇した場合は、この「[」をスキップして、次のレベルに戻り、上記の手順を繰り返します.
再帰的に展開し、「」に遭遇した場合、最下層の(k*res)を展開し、2番目の「」に遭遇した場合、次の階層を展開します.
注意:decode(s,i)を使用して再帰する場合、iが値伝達である場合、再帰は再帰前のi値+1になりますが、ここではiの現在のi値に1を加える必要があります.これにより、iはずっと後ろに進むことができます(参照伝達、C++に&i、Pythonにリストiが入ります).

3.コード実装

class Solution(object):
    def decode(self,s,i):
        res=""
        n=len(s)
        while i[0] < n and s[i[0]]!="]":
            #  
            if s[i[0]] < "0" or s[i[0]] > "9":
                res=res+s[i[0]]
                i[0]+=1
            #  
            else:
                if s[i[0]] <= "9" and s[i[0]] >= "0":
                    k = 0
                    while s[i[0]] <= "9" and s[i[0]] >= "0":
                        k = k * 10 + int(s[i[0]])
                        i[0]+= 1
                #  "["
                i[0]+= 1
                t=self.decode(s,i)
                #  "]"
                i[0]+=1
                while k > 0:
                    res+=t
                    k-=1
        return res
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        i = []
        i.append(0)
        return self.decode(s,i)