Giả sử chúng ta có hai chuỗi s và t, và hai giá trị p và q. Chúng ta phải kiểm tra xem liệu có thể lấy t từ s sao cho s được tách thành các nhóm p số ký tự ngoại trừ nhóm cuối cùng sẽ có ký tự ≤ p và chúng ta có thể chọn tối đa q số ký tự từ mỗi nhóm và thứ tự của các ký tự trong t cũng phải giống với s.
Vì vậy, nếu đầu vào là s ="mnonnopeqrst", t ="moprst", p =5, q =2, thì đầu ra sẽ là True vì chúng ta có thể thực hiện các phép chia như "mnonn", "opeqr", "st" Bây giờ, bằng cách lấy 2 chuỗi con ký tự "mo" và "pr" từ "mnonn" và "opeqr" thì "st" đã có ở đó nên bằng cách sử dụng hai chuỗi con có độ dài này, chúng ta có thể tạo t bằng cách nối đơn giản.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- temp:=một bản đồ trống chứa danh sách trống cho tất cả các khóa
- l:=một danh sách có kích thước bằng chiều dài của s và điền bằng 0
- đối với tôi trong phạm vi từ 0 đến kích thước của s, thực hiện
- chèn i vào cuối temp ['a']
- thấp:=0
- đối với tôi trong phạm vi từ 0 đến kích thước của t - 1, thực hiện
- chỉ số:=temp ['a']
- it:=chỉ mục để chèn mức thấp trong danh sách chỉ số để duy trì thứ tự đã sắp xếp
- nếu nó giống với kích thước của các chỉ số - 1, thì
- trả về Sai
- count:=thương số của (chỉ số [it] / p)
- l [count]:=l [count] + 1
- nếu l [count]> =q, thì
- count:=count + 1
- thấp:=count * p
- nếu không,
- thấp:=indices [it] + 1
- trả về True
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
from bisect import bisect_left from collections import defaultdict def solve(s, t, b, m) : temp = defaultdict(list) l = [0] * len(s) for i in range(len(s)) : temp['a'].append(i) low = 0 for i in range(len(t)) : indices = temp['a'] it = bisect_left(indices, low) if it == len(indices) : return False count = indices[it] // b l[count] = l[count] + 1 if l[count] >= m : count += 1 low = count * b else : low = indices[it] + 1 return True s = "mnonnopeqrst" t = "moprst" p = 5 q = 2 print (solve(s, t, p, q))
Đầu vào
"mnonnopeqrst", "moprst", 5, 2
Đầu ra
True