Giả sử chuỗi mã hóa S cho trước. Ta phải tìm và viết chuỗi giải mã ra băng, ở đây chuỗi mã hóa đọc từng ký tự và thực hiện các bước −
- Nếu ký tự đọc là chữ cái, chữ cái đó đơn giản được viết lên băng.
- Nếu ký tự đọc là chữ số, toàn bộ băng hiện tại được viết lại lặp lại digit - 1 lần thêm.
Bây giờ nếu chuỗi mã hóa S và chỉ mục K cho trước, tìm và trả về ký tự thứ K (chỉ mục từ 1) trong chuỗi giải mã.
Ví dụ chuỗi "hello2World3" và k = 10, kết quả "o". Vì chuỗi giải mã là "hellohelloWorldhellohelloWorldhellohelloWorld", ký tự thứ 10 là "o".
Để giải quyết, ta làm theo các bước −
- size := 0
- với i trong chuỗi s
- nếu i là chữ số, size := size * int(i), ngược lại size := size + 1
- với i từ len(s)-1 xuống 0
- k := k mod size
- nếu s[i] là chữ số và k = 0, trả về s[i]
- nếu s[i] là chữ cái, giảm size 1, ngược lại size := size / int(s[i])
- trả về chuỗi rỗng
Xem triển khai sau −
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)Kết quả
o