概要
長さが等しい二つの文字列 X, Y が次の条件を満たすとき、「変換可能」であるとする。
- アルファベットの順列を一つ選び P とする
- X[ i ] を P[ X[ i ] ] で置き換えたものが X と等しい
'A' 〜 'I' のアルファベットから成る二つの文字列 A, B が与えられる。
この二つの文字列に対し、次の操作ができる。
- インデックスを一つ選び、二つの文字列からその位置の文字を削除する
A, B を変換可能にするために必要な操作回数の最小値を求めよ。
解法
アルファベットが 9 種類しか無いことを利用します。
9! = 362,880 なので、アルファベットの順列を全通り試すことができます。
順列 P が決まったとき、P[ A[ i ] ] B[ i ] なる i の数が、削除しなければならない数です。
そのような値の内、最小のものが問題の答えです。
コード
typedef vector<int> VI; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define ALL( c ) (c).begin(), (c).end() class ConvertibleStrings { public: int leastRemovals( string A, string B ) { const int L = A.size(); VI mapping( 9 ); iota( ALL( mapping ), 0 ); int res = INT_MAX; do { int tmp = 0; REP( i, 0, L ) { tmp += mapping[ A[i] - 'A' ] != B[i] - 'A'; } res = min( res, tmp ); } while ( next_permutation( ALL( mapping ) ) ); return res; } };