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

割と典型なのかもしれないけどちょっと手間取った。
http://yukicoder.me/problems/610

問題

N文字の文字列SとM文字の文字列Tが与えられる。
Sに以下の処理を行い、Tにしたい。
最小何回処理を行えばよいか。

• Sの任意の１文字を他の文字に変える
• Sの任意の１文字を削除する
• Sの任意の位置に任意の１文字を追加する

解法

放送を見てこんなのを知った。
レーベンシュタイン距離 - Wikipedia

LCSのアレンジ問題。
f(x,y)をSのx文字以降とTのy文字以降を一致させるのにかかる最小処理回数とする。

f(N,M)=0からDPでf(0,0)を求めていく。

• S[x]==T[y]なら、f(x,y)=f(x+1,y+1)
• そうでない場合、f(x,y)は以下の最小値
  • S[x]を消すと考えて f(x+1,y)+1
  • T[y]を頭に追加すると考えて f(x,y+1)+1
  • T[y]をS[x]に置き換えると考えて f(x+1,y+1)+1

int N,M;
string S,T;
int dp[1010][1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>S>>T;
	for(x=N;x>=0;x--) for(y=M;y>=0;y--) {
		if(x==N && y==M) continue;
		if(x<N && y<M && S[x]==T[y]) dp[x][y]=dp[x+1][y+1];
		else {
			dp[x][y]=N+M;
			if(x<N) dp[x][y]=min(dp[x][y],dp[x+1][y]+1);
			if(y<M) dp[x][y]=min(dp[x][y],dp[x][y+1]+1);
			if(x<N && y<M) dp[x][y]=min(dp[x][y],dp[x+1][y+1]+1);
		}
	}
	
	cout<<dp[0][0]<<endl;
}

まとめ

ABCで出たって…？