Giả sử chúng ta có một chuỗi s, đây là mã hóa một chuỗi dài hơn. s được biểu diễn dưới dạng nối của n (t), n (t) biểu diễn nối của t, n lần và t là một chuỗi thông thường hoặc nó là một chuỗi được mã hóa đệ quy khác. Chúng tôi phải tìm phiên bản đã giải mã của s.
Vì vậy, nếu đầu vào giống như s ="3 (pi) 2 (3 (am)) 0 (f) 1 (u)", thì đầu ra sẽ là "pipipiamamamamamamamu"
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
i:=0
-
Định nghĩa một hàm phân tích cú pháp (). Điều này sẽ mất
-
ans:=một danh sách mới
-
trong khi i
-
nếu s [i] là một chữ số thì
-
d:=0
-
trong khi s [i] là chữ số, do
-
d:=10 * d + phần nguyên của s [i]
-
i:=i + 1
-
-
i:=i + 1
-
phân đoạn:=parse ()
-
i:=i + 1
-
chèn phân đoạn d lần vào ans
-
-
nếu không,
-
chèn s [i] vào cuối ans
-
i:=i + 1
-
-
-
trả về chuỗi sau khi tham gia các mục của ans
-
Từ phương thức chính trả về parse ()
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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 segment = parse() i += 1 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