操作は \(1\) 文字ずつ独立に行われるので、\(S\) 全体を \(T\) に一致させられる条件は次のようになります。

• すべての \(i\) \((1 \leq i \leq |S|)\) について次の命題が成り立つ：
  • \(S_i\) を似ている文字に置き換え続けて \(T_i\) に変更することができる。

よってこの問題を解くには、次の部分問題を正しく判定できればよいです。

• 文字 \(u\) を似ている文字に置き換え続けて \(v\) に変更することができますか？

言い換えた後の問題をグラフの問題に言い換えます。a,b, \(\dots\), z というラベルが貼られた \(26\) 頂点のグラフがあって、似ている文字の間には辺が張られているとします。すると、ある文字を似ている文字に置き換える操作は、グラフ上の辺で結ばれた頂点の一方から他方に移動する操作に言い換えられます。よって、部分問題をグラフの問題に言い換えると「頂点 \(u\) から辺をたどって頂点 \(v\) へ移動できるか？」というような頂点同士の連結性を判定する問題になります。

グラフの連結性は DFS や BFS などのグラフ探索アルゴリズムや Union-Find のようなグラフを管理するデータ構造を利用して高速に判定することができます。よって部分問題が高速に解けて、これを利用して問題全体も解くことができます。
計算量は \(\sigma = 26\) として \(\mathrm{O}((N + \sigma) |S|)\) 程度です。