Cho chuỗi s mã hóa dạng n(t): n(t) nghĩa là lặp lại t n lần, t có thể là chuỗi thường hoặc chuỗi mã hóa đệ quy. Giải mã s.
Ví dụ: s = "3(pi)2(3(am))0(f)1(u)" → "pipipiamamamamamamu".
Giải pháp
Parser đệ quy với con trỏ toàn cục i:
- parse(): đọc đến khi hết chuỗi hoặc gặp ')'
- Nếu gặp chữ số: đọc số d, bỏ qua '(', đệ quy parse() lấy segment, bỏ qua ')', thêm segment d lần
- Nếu ký tự thường: thêm vào kết quả
Ví dụ minh họa
class Solution:
def solve(self, s):
i = 0
def parse():
nonlocal i
ans = []
while i < len(s) and s[i] != ")":
if s[i].isdigit():
d = 0
while s[i].isdigit():
d = 10 * d + int(s[i])
i += 1
i += 1 # skip '('
segment = parse()
i += 1 # skip ')'
ans.extend(segment for _ in range(d))
else:
ans.append(s[i])
i += 1
return "".join(ans)
return parse()
ob = Solution()
s = "3(pi)2(3(am))0(f)1(u)"
print(ob.solve(s))
Đầu vào
"3(pi)2(3(am))0(f)1(u)"
Đầu ra
pipipiamamamamamamu