計算量の説明のため，文字列長の最大値を \(S\) と書くことにします．

単語を頂点とするグラフを考え，変換可能な 2 単語間に辺を張ったグラフを考えると，本問題は最短経路問題として定式化できます． よって，

(1) グラフのどの頂点の間に辺があるかを調べる

(2) 最短路を計算する．

という手順で解くことができます．

(1) は，\(\binom{N+2}{2}\) 通りすべてを調べるという方法により \(O(N^2S)\) 時間で行えます．(2) は BFS により \(O(N^2)\) 時間で行えます（\(N^2\) は辺の個数の上限 \(\binom{N+2}{2}\) からきています）．

以上により，時間計算量 \(O(N^2S)\) で解くことができます．

時間計算量 \(O(NS)\) で解く方法を紹介します．

head -> heal -> teal -> tell と変換する代わりに，

head -> hea* -> heal -> *eal -> teal -> te*l -> tell

と変換することを考えます．間に挟むワイルドカード付の単語を特殊文字列と呼びましょう．元の文字列と特殊文字列を頂点とし，変換可能な文字列・特殊文字列の間に辺を張ったグラフを考えて最短経路問題を解けば，その半分が元の問題の解になります．

考えるべき特殊文字列は，入力に現れる文字列の 1 文字をワイルドカードに置換した \(O(NS)\) 個です．このグラフの辺の個数も，各文字列から \(S\) 個の特殊文字列に向かう \(O(NS)\) 個です．

よって頂点数・辺の個数が \(O(NS)\) のグラフで最短経路問題を解くことに帰着できて，時間計算量 \(O(NS)\) が達成できます．