Đầu tiên ta dựng một trie của ~N~ từ. Trạng thái ban đầu là ở gốc của trie; thao tác thêm một kí tự tương đương với việc đi xuống một nút con, xóa một kí tự tương đương với việc đi lên nút cha. Khi ta đi đến một nút là kết thúc của một từ, ta sẽ in từ đó ra.

Giờ xét một phiên bản khác đơn giản hơn của bài toán gốc: Vẫn là tìm số bước nhỏ nhất để in ra mọi từ nhưng sau khi in ra từ cuối cùng thì phải xóa hết các kí tự còn lại của máy in (tương đương với cuối cùng phải đi lên gốc trie).

Ta cũng xây dựng bài toán này trên trie, ta nhận thấy với mọi cạnh trên trie, sẽ có một lúc nào đó ta phải đi xuống cạnh đó để đến các nút con ở dưới, và sau đó ta phải đi vòng lên qua cạnh đó.

Điều này có nghĩa là mỗi cạnh trên trie sẽ được đi qua ít nhất hai lần. Do đó giải pháp sử dụng mỗi cạnh đúng hai lần sẽ là tối ưu nhất. Ta có thể làm điều này đơn giản bằng cách DFS trên trie (duyệt theo chiều sâu).

Quay lại bài toán ban đầu, rõ ràng so với bài toán trên, điểm khác biệt duy nhất là ta có loại bỏ các thao tác xóa ở cuối, ta có thể dừng ngay khi in ra từ cuối cùng. Vì vậy chúng ta nên tối ưu hóa độ dài của từ cuối cùng. Và chúng ta luôn có cách để kết thúc ở từ dài nhất.

Ta có thể thực hiện thuật toán như sau: Đầu tiên, xác định một từ dài nhất mà bạn muốn in ra. Sau đó ta thực hiện DFS, nếu nút hiện tại nằm trên đường đi của từ dài nhất đó, ta sẽ thực hiện in các từ thuộc các nhánh không thuộc từ dài nhất đó trước, sau đó mới đi tiếp vào nhánh con thuộc từ dài nhất.

Code mẫu: https://ideone.com/rlQAim