Decode Nested Repeat
Programming Interview
Hard
5 views
Problem Description
A string is provided in form like 3[a2[c]] where number means repeat. Decode and output the final string.
Input Format
One line encoded.
Output Format
One line decoded.
Constraints
Total decoded length
Official Solution
import sys
s=sys.stdin.read().strip()
if not s: sys.exit(0)
num=0
stack=[]
cur=[]
for ch in s:
if '0'<=ch<='9':
num=num*10 + (ord(ch)-48)
elif ch=='[':
stack.append((cur,num if num!=0 else 1))
cur=[]
num=0
elif ch==']':
prev,k=stack.pop() if stack else ([],1)
cur=prev + cur*k
if len(cur)>200000:
cur=cur[:200000]
else:
cur.append(ch)
res=''.join(cur)
sys.stdout.write(res[:200000])
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!