Giả sử chúng ta có hai chuỗi không rỗng s và t có cùng độ dài. Chúng ta phải phân chia chúng thành các chuỗi con sao cho mỗi cặp chuỗi con s và t có cùng kích thước và chúng là đảo ngữ của nhau. Bây giờ hãy tìm các chỉ số cắt sao cho nó tạo ra số lần cắt tối đa là s và t. Nếu không tìm thấy kết quả nào, hãy trả về danh sách trống.
Vì vậy, nếu đầu vào là s ="bowcattiger" t ="owbactietgr", thì đầu ra sẽ là [0, 3, 5, 6, 10], vì chúng ta có thể phân chia chuỗi thành 5 phân vùng sao cho mỗi chuỗi là một đảo ngữ của nhau. s =["bow", "ca", "t", "tige", "r"], t =["owb", "ac", "t", "ietg", "r"]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- khoảng thời gian:=một danh sách mới
- cs:=một bản đồ với ký tự hiện diện trong s và tần suất của nó
- ct:=một bản đồ có ký tự ở dạng t và tần số của nó
- nếu cs không giống với ct, thì
- trả lại một danh sách mới
- đối với x trong phạm vi kích thước s-1 xuống 0, thực hiện
- cs [s [x]]:=cs [s [x]] - 1
- ct [t [x]]:=ct [t [x]] - 1
- nếu cs giống với ct, thì
- chèn x vào cuối các khoảng
- sắp xếp các khoảng thời gian trong danh sách và trả về
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
from collections import Counter class Solution: def solve(self, a, b): intervals = [] ca = Counter(a) cb = Counter(b) if ca != cb: return [] for x in reversed(range(len(a))): ca[a[x]] -= 1 cb[b[x]] -= 1 if ca == cb: intervals.append(x) return sorted(intervals) ob = Solution() s = "bowcattiger" t = "owbactietgr" print(ob.solve(s, t))
Đầu vào
"bowcattiger", "owbactietgr"
Đầu ra
[0, 3, 5, 6, 10]