P1688 New Word Ladder Problem

Given a dictionary that contains $n$ words, define the dictionary order as the order within this dictionary (i.e., the given list order). Select some words and form a word ladder in dictionary order so that the ladder length is maximized. Rules for the new word ladder: 1. Word transformation: from $w_i$, adding one letter, deleting one letter, or changing one letter can obtain $w_{i+1}$. 2. Dictionary-order chain: $w_1, w_2, \cdots, w_k$ are in dictionary order.

The first line contains an integer $n$ ($1 \le n \le 25,000$), the total number of words in the dictionary. The next $n$ lines, in dictionary order, contain $n$ words, one string per line. Each word consists only of lowercase letters, and its length is between $1$ and $16$ inclusive.

Output a single integer on one line, the maximum possible length of the word ladder.

Sample explanation: A word ladder of length $5$ is: $\texttt{dig}\to \texttt{fig}\to \texttt{fin}\to \texttt{fine}\to \texttt{wine}$. Translated by ChatGPT 5