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)
一時結果変数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)
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)