Giả sử một chuỗi được mã hóa S được đưa ra. Chúng ta phải tìm và ghi chuỗi đã giải mã vào một băng, ở đây, chuỗi được mã hóa được đọc từng ký tự một và thực hiện các bước sau -
- Nếu ký tự được đọc là một chữ cái, thì chữ cái đó chỉ được ghi vào băng.
- Nếu ký tự được đọc là một chữ số, thì toàn bộ đoạn băng hiện tại sẽ được viết lặp lại một chữ số - tổng cộng thêm 1 lần.
Bây giờ nếu một số chuỗi được mã hóa S và một chỉ số K được đưa ra, hãy tìm và trả về ký tự thứ K (chỉ số bắt đầu từ 1) trong chuỗi được giải mã.
Vì vậy, nếu chuỗi là “hello2World3” và k =10, thì đầu ra sẽ là “o”. Điều này là do chuỗi được giải mã sẽ là “hellohelloWorldhellohelloWorldhellohelloWorld”, vì vậy ký tự thứ 10 là “o”.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- kích thước:=0
- cho tôi trong chuỗi s
- nếu tôi là một ký tự số, thì kích thước:=size * số nguyên của tôi, nếu không thì kích thước:=size + 1
- cho tôi trong phạm vi độ dài từ s - 1 xuống 0
- k:=k kích thước mod
- nếu s [i] là số và k =0, thì trả về s [i]
- nếu s [i] là số thì hãy giảm kích thước đi 1, nếu không thì size:=size / integer của s [i]
- trả về chuỗi trống
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution(object):
def decodeAtIndex(self, s, k):
"""
:type S: str
:type K: int
:rtype: str
"""
size = 0
for i in s:
if i.isdigit():
size *= int(i)
else:
size += 1
#print(size)
for i in range(len(s) - 1, -1, -1):
k %= size
if s[i].isalpha() and k == 0:
return s[i]
if s[i].isalpha():
size -=1
else:
size /= int(s[i])
return ""
ob = Solution()
print(ob.decodeAtIndex("hello2World3", 10)) Đầu vào
"hello2World3"
10
ob.decodeAtIndex("hello2World3", 10) Đầu ra
o