Phân tích

Có nhiều cách tiếp cận khả thi cho bài toán này. Đối với bộ test nhỏ, ta có thể sử dụng phương pháp quy hoạch động để tính toán cho mỗi tiền tố của chuỗi đã cho, số lần thay thế ít nhất cần thiết để tạo thành tiền tố này sao cho lần thay thế cuối cùng cách đây \(k\) ký tự, với \(k = 1, 2, 3, \dots\)

Ví dụ, với từ "codejam", chúng ta sẽ thấy rằng "c" không thể được tạo thành mà không có sự thay thế, nhưng có thể được tạo thành (ví dụ từ "a") bằng một sự thay thế cách đó 1 ký tự. Chúng ta tìm thấy điều này bằng cách duyệt qua tất cả các từ trong từ điển. Sau đó, chúng ta duyệt qua tất cả các từ trong từ điển để thử tạo thành "co" (chúng ta có thể làm điều này, ví dụ, từ "do" với một sự thay thế cách đó 2 ký tự). Chúng ta cũng có thể xem xét các từ có một chữ cái để mở rộng chữ "c" mà chúng ta đã biết cách tạo, nhưng điều này sẽ không hiệu quả vì "o" không phải là một từ, và chúng ta đang ở quá gần lần thay thế cuối cùng. Tiếp theo là "cod", thực tế là một từ, vì vậy có thể được tạo thành với không có sự thay thế nào. Tiếp theo là "code" — đối với từ này chúng ta có nhiều lựa chọn, như kết hợp "c" mà chúng ta biết cách tạo và "ode", hoặc "cod" và một sự thay thế để tạo thành "e" từ "a", hoặc — cách tốt nhất, vì không yêu cầu thay thế nào — chỉ cần sử dụng từ "code".

Theo cách này, đối với mỗi tiền tố và mỗi khoảng cách của lần thay thế cuối cùng, chúng ta có thể tìm ra số lượng thay thế ít nhất cần thiết để tạo thành tiền tố này bằng cách xem xét tất cả các tiền tố nhỏ hơn (bao gồm cả tiền tố rỗng), tất cả các từ trong từ điển nhỏ hơn hoặc bằng 10 ký tự, và tìm hiểu xem liệu chúng ta có thể kết hợp chúng hay không.

Đối với bộ test lớn, chúng ta không thể duyệt qua toàn bộ từ điển thường xuyên như vậy. Vì vậy, chúng ta bắt đầu bằng cách xây dựng một bảng băm (hash table) hoặc một cây tiền tố (Trie). Đối với mỗi từ trong từ điển, chúng ta chèn từ đó vào cấu trúc dữ liệu, và cũng chèn từ đó với mỗi tập hợp các chữ cái bị thay đổi có thể có trong từ được thay thế bằng các ký tự '*'. Tuy nhiên, cách tiếp cận hiệu quả hơn là sử dụng Trie để lưu trữ từ điển.

Tiếp theo, chúng ta sử dụng quy hoạch động để xây dựng một bảng chứa, cho mỗi tiền tố của email và vị trí trong tiền tố đó của chữ cái bị thay đổi cuối cùng, số lượng thay đổi tối thiểu cần thiết để chuyển đổi một chuỗi các từ trong từ điển thành tiền tố đó, nếu có thể. (Để tiết kiệm thời gian, chúng ta có thể gộp tất cả các trạng thái cho một tiền tố mà chữ cái bị thay đổi cuối cùng cách cuối tiền tố từ 5 vị trí trở lên, bởi vì nếu chữ cái bị thay đổi cuối cùng cách đó hơn 4 vị trí, thì việc nó cách bao xa không còn quan trọng đối với các từ tiếp theo.)

Gọi \(dp[i][j]\) là số lần thay đổi tối thiểu để khớp \(i\) ký tự đầu tiên của \(S\), với \(j\) là số ký tự tính từ vị trí thay đổi cuối cùng đến vị trí \(i\) (nếu \(j \ge 4\), ta coi như \(j = 4\) để giảm trạng thái).

Mỗi trạng thái có thể có tương ứng với một giải pháp từng phần. Chúng ta xem xét từng cách có thể để thêm một từ nữa nhằm tạo ra một giải pháp từng phần dài hơn. Để làm điều này, chúng ta thử từng tổ hợp của:

• Độ dài của từ tiếp theo, \(L\) (\(1 \le L \le 10\)).
• Mỗi tập hợp các vị trí có thể có của các chữ cái bị thay đổi trong từ tiếp theo, đảm bảo khoảng cách giữa các lần thay đổi (kể cả với lần thay đổi cuối cùng ở từ trước đó) ít nhất là 5.

Đối với mỗi tổ hợp này, chúng ta kiểm tra xem từ được tạo ra có tồn tại trong từ điển hay không. Nếu có, chúng ta có thể cập nhật bảng DP.

Để tối ưu hóa, thay vì duyệt mọi từ trong từ điển cho mỗi vị trí \(i\), ta có thể duyệt trên cây Trie bắt đầu từ vị trí \(i\) trong chuỗi \(S\). Khi duyệt trên Trie, ta cho phép sai khác ký tự nếu khoảng cách từ lần thay đổi trước đó đủ lớn.

Đáp án là giá trị nhỏ nhất trong các trạng thái \(dp[n][j]\) với \(n\) là độ dài toàn bộ email.

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