Leetcode - 字符串转换

问题

给定两个字符串 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对字符使用插入、删除与替换。

思路

对于类似第一时间想不出解法的问题，首先考虑动态规划。设dp[i][j]代表从长度i的字符串转换为长度j的字符串需要的最少操作数，若word1[i-1]==word2[j-1]，则显然最后一个字符无需任何操作，因此dp[i][j]=dp[i-1][j-1]。若word1[i-1]!=word2[j-1]，则最后一位字符需要一次操作，插入操作对应dp[i][j-1]，删除操作对应dp[i-1][j]，替换操作对应dp[i-1][j-1]，此时的状态方程为dp[i][j]=min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1。

代码(C++)

int m=word1.length();
int n=word2.length();
int dp[m+1][n+1];
for(int i=0;i<=m;i++)	//显然需要i次删除操作
	dp[i][0]=i;
for(int j=0;j<=n;j++)	//显然需要j次插入操作
	dp[0][j]=j;	
for(int i=0;i<m;i++)	//长度比次序大一
	for(int j=0;j<n;j++)
	{
		if(word1[i]==word2[j])
			dp[i+1][j+1]=dp[i][j]	//字符0对应长度1，类推
		else
			dp[i+1][j+1]=min(min(dp[i+1][j],dp[i][j+1]),dp[i][j])+1;
	}
return dp[m][n];