Chương trình phân hoạch hai chuỗi sao cho mỗi phân đoạn tạo thành anagram trong Python

Giả sử chúng ta có hai chuỗi không rỗng s và t có cùng độ dài. Chúng ta cần phân hoạch chúng thành các chuỗi con sao cho mỗi cặp chuỗi con của s và t có cùng kích thước và là anagram của nhau. Tìm các chỉ số cắt để có số lượng phân đoạn tối đa. Nếu không tìm thấy kết quả, trả về danh sách rỗng.

Ví dụ, nếu đầu vào là s = "bowcattiger", t = "owbactietgr", thì đầu ra sẽ là [0, 3, 5, 6, 10], vì ta có thể phân hoạch chuỗi thành 5 phân đoạn sao cho mỗi chuỗi con là anagram của nhau: s = ["bow", "ca", "t", "tige", "r"], t = ["owb", "ac", "t", "ietg", "r"].

Các bước giải quyết:

• Khởi tạo danh sách intervals rỗng.
• Tạo bản đồ tần suất ký tự cs cho s và ct cho t.
• Nếu cs khác ct, trả về danh sách rỗng.
• Duyệt x từ độ dài của s - 1 xuống 0:
  • Giảm tần suất của s[x] trong cs và t[x] trong ct.
  • Nếu cs bằng ct, thêm x vào intervals.
• Sắp xếp intervals và trả về.

Ví dụ minh họa

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]