Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character b) Delete a character
c) Replace a character
思路 dp:
有删除操作比较麻烦
换位思考一下变为字符串对齐的问题
有两个字符串 一个为s 一个为t；
对应的位置相同不扣分 不同则扣一分
两个特殊符号'-'不会对应
S位置的'-'代表增加字符
T位置的'-'代表删除字符
我们最终的目的是使扣分最少
dp[i][j]表示s的前i个位置和T的前j个位置对齐的最少得分
dp[i][j]=min(dp[i-1][j-1]+sames(i,j),dp[i-1][j]+1,dp[i][j-1]+1);
sames(i,j)表示的是i位置和J位置的字符是否相同 如果相同为0 不相同为1；
dp[i-1][j-1]+sames(i,j)对应的是第i个字符和第J个字符对齐
dp[i-1][j]+1 表示的是第i个字符和-对齐 所以需要删掉第i个字符
dp[i][j-1]+1表示的是个j个字符和'-'对齐 需要加入该字符
dp[0][j>0]=j 表示的是没有字符跟s字符相同 需要进行j次操作
AC代码
public class Solution { public int minDistance(String word1, String word2) { int n=word1.length(); int m=word2.length(); char a[]=word1.toCharArray(); char b[]=word2.toCharArray(); int dp[][]=new int[n+1][m+1]; for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ if(i==0){ dp[i][j]=j; }else if(j==0){ dp[i][j]=i; }else{ dp[i][j]=Math.min(dp[i-1][j-1]+(a[i-1]==b[j-1]?0:1),Math.min(dp[i-1][j]+1,dp[i][j-1]+1)); } } } return dp[n][m]; } }
