Kiểm tra từ có tồn tại trong lưới ký tự hay không bằng Python

Giả sử có một lưới (ma trận) các ký tự. Cần kiểm tra xem một từ cho trước có xuất hiện trong lưới hay không. Từ có thể tìm thấy theo 4 hướng: ngang trái/phải và dọc lên/xuống. Trả về True nếu tìm thấy, ngược lại False.

Ví dụ với lưới sau và từ "python":

Kết quả: True.

Thuật toán

• Định nghĩa hàm find_grid() nhận ma trận, chuỗi đầu vào, vị trí hàng/cột, số hàng/cột, độ sâu (degree).
• Nếu degree bằng độ dài chuỗi → trả về True.
• Nếu vị trí vượt biên → trả về False.
• Nếu ký tự tại vị trí khớp với ký tự trong chuỗi tại degree:
  • Lưu ký tự tạm, thay bằng '#' để đánh dấu đã dùng.
  • Đệ quy kiểm tra 4 hướng (trên, dưới, trái, phải) với degree+1, kết hợp bằng OR bitwise.
  • Khôi phục ký tự, trả về kết quả.
• Ngược lại trả về False.
• Hàm chính: nếu độ dài chuỗi > tổng ô → False. Duyệt từng ô, nếu ký tự đầu khớp thì gọi find_grid. Nếu True thì trả về True. Cuối cùng trả về False.

Ví dụ code

def find_grid(matrix, input_str, row_pos, col_pos, row_count, col_count, degree):
    if degree == len(input_str):
        return True
    if row_pos < 0 or col_pos < 0 or row_pos >= row_count or col_pos >= col_count:
        return False
    if matrix[row_pos][col_pos] == input_str[degree]:
        temp = matrix[row_pos][col_pos]
        # Thay thế ký tự đã dùng (cần xử lý vì string immutable, ví dụ dùng list)
        matrix[row_pos] = matrix[row_pos][:col_pos] + '#' + matrix[row_pos][col_pos+1:]
        result = (find_grid(matrix, input_str, row_pos-1, col_pos, row_count, col_count, degree+1) |
                  find_grid(matrix, input_str, row_pos+1, col_pos, row_count, col_count, degree+1) |
                  find_grid(matrix, input_str, row_pos, col_pos-1, row_count, col_count, degree+1) |
                  find_grid(matrix, input_str, row_pos, col_pos+1, row_count, col_count, degree+1))
        matrix[row_pos] = matrix[row_pos][:col_pos] + temp + matrix[row_pos][col_pos+1:]
        return result
    else:
        return False

def solve(matrix, input_str, row_count, col_count):
    if len(input_str) > row_count * col_count:
        return False
    for row in range(row_count):
        for col in range(col_count):
            if matrix[row][col] == input_str[0]:
                if find_grid(matrix, input_str, row, col, row_count, col_count, 0):
                    return True
    return False

word_grid = ["pghsf", "ykdgh", "tkghi", "hnsjs", "ojfgh", "nrtyu"]
print(solve(word_grid, "python", 6, 5))

Đầu vào

["pghsf", "ykdgh", "tkghi", "hnsjs", "ojfgh", "nrtyu"], "python"

Đầu ra

True