Chương trình kiểm tra có thể đảo ngược dãy con để biến list này thành list kia trong Python

Cho hai danh sách và . Có thể lấy dãy con bất kỳ của và đảo ngược nó bất kỳ số lần. Kiểm tra có thể biến thành không.

Ví dụ: , → True (đảo [2,3,4] và [9,10]).

Giải thuật (Kiểm tra cùng multiset)

Việc đảo ngược dãy con bất kỳ lần cho phép hoán vị tùy ý → chỉ cần kiểm tra và có cùng multiset (tần suất phần tử) hay không.

1. Đếm tần suất → .
2. Trừ tần suất từ .
3. Trả về nếu tất cả giá trị trong bằng 0.

Ví dụ minh họa

from collections import defaultdict

class Solution:
    def solve(self, nums, target):
        res = defaultdict(int)
        for n in nums:
            res[n] += 1
        for t in target:
            res[t] -= 1
        return all(v == 0 for v in res.values())

ob = Solution()
A = [2, 3, 4, 9, 10]
B = [4, 3, 2, 10, 9]
print(ob.solve(A, B))  # Output: True

Đầu vào

[2, 3, 4, 9, 10], [4, 3, 2, 10, 9]

Đầu ra

True