ことさら−古都プログラマーの更級日記

京都でお寺を回りながら御朱印集めをしていたエンジニアのブログ。おもに技術的なはなしとか日常的なはなし。たまにカメラの話や競馬の話も書きます。

yukicoder No.225 文字列変更(medium)

解き方わかっていたのに、配列初期化をちゃんとできていなかったり、変換前と変換後を逆にしていたりなどでバグらせてしまい、時間内に提出できませんでした…(終了3分後に解けました…)

解法としてはDPする感じです。蟻本で最長共通部分列問題というのを調べてみればいいみたいです。なんとなくソースコードみて察してください。

ソースコード

int main(int argc, const char * argv[]){
    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    int editCount[1001][1001];
    int inf = 1<<28;
    REP(i, n+1) {
        REP(j, m+1) {
            editCount[i][j] = inf;
        }
    }
    editCount[0][0] = 0;
    
    REP(i, n+1) {
        REP(j, m+1) {
            // 文字を追加する
            if(i <= n) {
                editCount[i][j+1] = min(editCount[i][j+1], editCount[i][j] + 1);
            }
            
            // 文字を削除する
            if(j <= m) {
                editCount[i+1][j] = min(editCount[i+1][j], editCount[i][j] + 1);
            }
            
            // 文字を変更する
            if(s[i] == t[j]) {
                editCount[i+1][j+1] = min(editCount[i+1][j+1], editCount[i][j]);
            } else {
                editCount[i+1][j+1] = min(editCount[i+1][j+1], editCount[i][j] + 1);
                
            }
        }
    }
    
    cout << editCount[n][m];
}