候補のリストをメンテナンスする
上記の問題、公式解説では、「0 〜 9 を重複なく割り当てられる文字は最大でも10種類なので、10! 通りを端から順に調べる」という方針が説明されていますが、単純なしらみつぶしではなく、N1 + N2 = N3 という条件を考慮しながら割り当て方法の候補を作ることで、さらに計算量を削減することができます。
具体的には、a 〜 z に対応する数字を一列ならべたリスト（対応する数字がない部分は None を入れておく）を「対応表」として、考え得る対応表を詰め込んだリスト candidate を用意します。はじめは、candidate は空です。
はじめに、S1 の 1 の位の文字を見て、その文字に 0 〜 9 を割り当てた 10 種類の対応表を candidate に詰め込みます。
次に、candidate 内のそれぞれの対応表に対して、S2 の 1 の位の文字を見て、その文字に 0 〜9 を割り当てて、対応表を更新します。重複する割り当てはスキップします。（この時点で 10*9 通りの対応表が candidate に詰まっています。）
続いて、candidate 内のそれぞれの対応表に対して、対応表の割り当てを用いて、N1+N2 の 1 の位を計算します。S3 の 1 の位の文字には、この値のみが割り当てられます。うまく割り当てができない場合は、その対応表は破棄します。
・・・という処理を 1 の位、10 の位、100 の位・・・と行っていきます。適切な割り当てができなくなった候補はどんどん破棄されるので、それぞれの位における候補の数は、200 〜 300 個程度に抑えられます。最終的に残った候補の 1 つを答えればOKです。
実際のコードはこちらになります。
S1, S2, S3 の桁数が異なる場合は、上の桁の足りない部分を仮想的な「0番目の文字」として処理しており、a 〜 z を 1 番目〜26番目の文字として、「0番目の文字」を含めた対応表を使っています。一番上の桁まで処理した時に、対応を埋めきれていない候補が残っている可能性もあるため、最後に残った候補については、１つずつ「検算」して、検算に通ったものを答えとして表示しています。
