寝癖頭の解法

学習中の覚え書きを投稿、更新していきます。

Aizu Online Judge in C++ #DPL_1_E : Edit Distance (Levenshtein Distance)

Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。

・問題 "Edit Distance (Levenshtein Distance)"
https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_E
・編集距離

僕が作成、提出したコードは、以下のとおりです。

Aizu Online Judge in C++ #DPL_1_E : Edit Distance (Levenshtein Distance)
/*
Aizu Online Judge in C++ #DPL_1_E : Edit Distance (Levenshtein Distance)
https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_E
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    string s1,s2;
    cin>>s1>>s2;
    int ss1=(int)s1.size();
    int ss2=(int)s2.size();
    vector<vector<int> > dp(ss1+1,vector<int>(ss2+1));
    for(int i=0;i<=ss1;i++){
        dp[i][0]=i;
    }
    for(int i=0;i<=ss2;i++){
        dp[0][i]=i;
    }
    for(int i=1;i<=ss1;i++){
        for(int j=1;j<=ss2;j++){
            int Delete=dp[i-1][j]+1;
            int Insert=dp[i][j-1]+1;
            int Change=dp[i-1][j-1]+((s1[i-1]==s2[j-1]) ? 0 : 1);
            dp[i][j]=min({Delete,Insert,Change});
        }
    }
    cout<<dp[ss1][ss2]<<endl;
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/