貪欲法 ABC370 C - Word Ladderを理解し忘れないようにする

https://atcoder.jp/contests/abc370/tasks/abc370_c

問題概要

文字列S,Tが与えられ空配列Xに以下を行う。
SとTが等しくなるまでSを1文字書き換えたものを配列Xの末尾に追加すする。この際、Sの書き換える文字の順番はどこから書き換えても良い。
この手順終了後の配列Xのサイズ、配列の中身を辞書順で表示する。
また要素数最小のものが複数考えられる場合は、そのうち辞書順最小のものを求める

基本設計

• S,Tは100文字だから最大4回ループを回せる。
• Xに1回追加する際に、辞書順最小の文字列を詰めたいので、追加する文字列の全パターンを試した上でその中の辞書順最小文字列をXに追加する。
  • 計算量はs,tの文字数N個と全パターン試す際のN回で$O(N^2)$

回答コード

https://atcoder.jp/contests/abc370/submissions/57574523

提出コード

// 省略

int main()
{
  string s,t;
  cin >> s >> t;
  vector<string> x;
  int n = s.size();
  while (s != t)
  {
    string best;
    rep(i,n) if (s[i] != t[i]) {
      string ns = s;
      ns[i] = t[i];
      if (best == "") best = ns;
      else best = min(best,ns);
    }
    s = best;
    x.push_back(s);
  }
  cout << x.size() << endl;
  for(string s:x) cout << s << endl;
  return 0;
}