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

A,Bは素早く回答できたので特になし

C

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

問題概要

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

ハマった点

また要素数最小のものが複数考えられる場合は、そのうち辞書順最小のものを求める、これをどうコードに落とし込むのかを明確化できず

解説見た

1回の文字変換を行う際に全てのindex番号で試して、その中で辞書順最小のものをXに追加すればいい。
S==Tになった時点で終了し、答えを出力する。
こういった問題の要素を複数の部分問題に分割し、それぞれを独立に評価を行い、評価値の高い順に取り込んでいくことを貪欲法という。

解説放送コードより抜粋↓

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);
  }

1. s != tであればループを回す
2. |s,t|の全てのindex番号分試して最小のものを配列xに格納＋sを辞書順最小の文字列に更新
3. 1に戻る

参考元

解説放送

回答コード

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;
}