Kiểm tra các hàng ma trận là vòng xoay (circular rotations) của nhau trong Python

Cho ma trận vuông n×n. Kiểm tra hàng i là vòng xoay của hàng i-1 (hàng 0 là vòng xoay của hàng n-1).

Ví dụ ma trận 4x4: hàng 0: B A D C; hàng 1: C B A D; hàng 2: D C B A; hàng 3: A D C B → True.

Thuật toán

• Ghép hàng 0 thành chuỗi concat với dấu phân cách (ví dụ '-B-A-D-C-').
• Nhân đôi chuỗi: concat = concat + concat (chứa tất cả vòng xoay).
• Với mỗi hàng i>0, ghép thành chuỗi curr_row cùng format.
• Kiểm tra curr_row có là substring của concat không.

Triển khai

def solve(matrix):
    concat = ""
    for i in range(len(matrix)):
        concat += "-" + str(matrix[0][i])
    concat += concat  # nhân đôi
    for i in range(1, len(matrix)):
        curr_row = ""
        for j in range(len(matrix[0])):
            curr_row += "-" + str(matrix[i][j])
        if concat.find(curr_row) == -1:
            return False
    return True

matrix = [['B','A','D','C'],
          ['C','B','A','D'],
          ['D','C','B','A'],
          ['A','D','C','B']]
print(solve(matrix))  # True

Đầu vào / Đầu ra

Input: [['B','A','D','C'], ['C','B','A','D'], ['D','C','B','A'], ['A','D','C','B']]
Output: True

Độ phức tạp: O(n²) thời gian, O(n) không gian.