Phân tích: Ngôn ngữ ngoài hành tinh

Đầu tiên, chúng ta lưu trữ tất cả các từ điển vào một mảng 2 chiều.
Sau đó, chúng ta đọc từng mẫu, phân tích (parse) nó và đếm xem có bao nhiêu từ khớp với mẫu đó.

Ý tưởng

Một cách khả thi để lưu trữ một mẫu là sử dụng mảng 2 chiều P[15][26]. P[i][j] là True chỉ khi mã thông báo thứ \(i\) chứa chữ cái thứ \(j\) của bảng chữ cái, ngược lại là False. Nói cách khác, P[i] là một bitmap (hoặc mảng đánh dấu) của các chữ cái có trong mã thông báo thứ \(i\).

Cách cài đặt

Việc phân tích mẫu có thể được thực hiện như sau:

• Đọc một ký tự c.
• Nếu c là (, đọc các ký tự cho đến khi gặp ). Các ký tự vừa đọc chính là các lựa chọn cho mã thông báo đó.
• Ngược lại, mã thông báo chỉ chứa duy nhất ký tự c.
• Đánh dấu các giá trị tương ứng trong P[i] cho các chữ cái có trong mã thông báo.

Để đếm số lượng từ khớp, chúng ta kiểm tra từng từ trong từ điển. Với mỗi từ, ta kiểm tra xem chữ cái thứ \(i\) của từ đó có nằm trong tập các chữ cái cho phép của mã thông báo P[i] hay không. Nếu tất cả các chữ cái của từ đều thỏa mãn, từ đó được tính là một khớp.

Ngoài ra, trong một số ngôn ngữ lập trình, bài toán này có thể được giải bằng cách biến đổi mẫu thành một biểu thức chính quy (regular expression). Ví dụ trong Python, bạn có thể thay thế ( và ) bằng [ và ], sau đó sử dụng thư viện re để khớp mẫu.

Độ phức tạp

Tổng độ phức tạp là \(O(N \times L \times D)\). Với các giới hạn của tập dữ liệu lớn (\(N=500, L=15, D=5000\)), tổng số phép tính rơi vào khoảng 37.5 triệu, hoàn toàn nằm trong giới hạn thời gian cho phép.

Dựa trên phân tích chính thức của Google Code Jam.