Giả sử, chúng ta được cung cấp một chuỗi 'input_str'. Bây giờ, chúng tôi được yêu cầu xác định mọi chuỗi con có thể có từ chuỗi đã cho, sau đó nối tất cả các chuỗi con với nhau theo một thứ tự từ vựng thành một chuỗi khác. Chúng tôi cũng được cung cấp một giá trị nguyên k. Nhiệm vụ của chúng ta là trả về ký tự ở chỉ mục k từ chuỗi được nối.
Vì vậy, nếu đầu vào là input_str ='pqrs', k =6, thì đầu ra sẽ là p
Các chuỗi con từ chuỗi đã cho theo thứ tự từ vựng là p, pq, pqr, pqrs, q, qr, qrs, r, rs, s.
Nếu chúng ta nối các chuỗi, nó sẽ trở thành ppqpqrpqrsqqrqrsrrss. Ở vị trí 6, chữ cái là 'p'. (lập chỉ mục bắt đầu từ 0).
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- stk_list:=một danh sách mới chứa một bộ tuple chứa một chuỗi trống và danh sách tất cả các chữ cái từ input_str
- trong khi stk_list không trống, hãy thực hiện
- pre:=xóa phần tử cuối cùng khỏi stk_list
- temp:=xóa phần tử cuối cùng khỏi stk_list
- if k
- trả lại trước [k]
- k:=k - kích thước của pre
- input_sorted:=một danh sách mới chứa các bộ giá trị chứa các chữ cái của input_str và vị trí của chúng trong input_str
- sắp xếp danh sách input_sorted dựa trên giá trị thứ hai của các bộ giá trị theo thứ tự giảm dần
- i:=0
- while i
- val:=input_sorted [i, 0]
- temp1:=[input_sorted [i, 1]]
- j:=i + 1
- while j
- chèn input_sorted [j, 1] vào cuối temp1
- j:=j + 1
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(input_str, k):
stk_list = [("",list(range(len(input_str))))]
while stk_list:
pre, temp = stk_list.pop()
if k < len(pre):
return pre[k]
k -= len(pre)
input_sorted = sorted([(input_str[i],i+1) for i in temp if i < len(input_str)], reverse=True)
i = 0
while i < len(input_sorted):
val = input_sorted[i][0]
temp1 = [input_sorted[i][1]]
j = i + 1
while j < len(input_sorted) and input_sorted[j][0]== val:
temp1.append(input_sorted[j][1])
j += 1
stk_list.append((pre+val, temp1))
i = j
return None
print(solve('pqrs', 6)) Đầu vào
'pqrs', 6
Đầu ra
p