Chương trình tạo mảng bằng cách nối các mảng con của mảng khác trong Python

Cho một mảng 2D gọi là groups và một mảng nums. Ta cần kiểm tra xem có thể chọn n mảng con không giao nhau từ mảng nums sao cho mảng con thứ i bằng groups[i] (chỉ số 0), và nếu i > 0, mảng con thứ (i-1) xuất hiện trước mảng con thứ i trong nums.

Ví dụ: với groups = [[2,-2,-2],[4,-3,0]] và nums = [1,-1,0,2,-2,-2,4,-3,0], kết quả là true vì group[0] xuất hiện từ chỉ số 3 đến 5 của nums và group[1] từ chỉ số 6 đến 8.

Giải thuật

1. Khởi tạo i := 0.
2. Với mỗi grp trong groups:
   • Duyệt j từ i đến len(nums) - 1:
     • Nếu mảng con nums[j:j+len(grp)] trùng với grp:
       • Cập nhật i := j + len(grp).
       • Thoát vòng lặp trong.
     • Nếu không tìm thấy sau khi duyệt hết: trả về False.
3. Trả về True.

Ví dụ minh họa

def solve(groups, nums):
    i = 0
    for grp in groups:
        for j in range(i, len(nums)):
            if nums[j:j+len(grp)] == grp:
                i = j + len(grp)
                break
        else:
            return False
    return True

groups = [[2,-2,-2],[4,-3,0]]
nums = [1,-1,0,2,-2,-2,4,-3,0]
print(solve(groups, nums))

Đầu vào

[[2,-2,-2],[4,-3,0]], [1,-1,0,2,-2,-2,4,-3,0]

Đầu ra

True