问题描述
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[i][j]表示word1的前i个字符与word2前j个字符匹配需要的最少操作次数。 状态转移方程： if word1[i]==word2[j] dp[i][j]=dp[i-1][j-1] if word1[i]!=word2[j] dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]) 代码如下：
public int minDistance(String word1, String word2) { if(word1==null&&word2==null||word1.equals(word2)) return 0; if(word1.length()==0) return word2.length(); if(word2.length()==0) return word1.length(); int[][]dp=new int[word1.length()+1][word2.length()+1]; for(int i=0;i<=word1.length();i++){ dp[i][0]=i; } for(int j=0;j<=word2.length();j++){ dp[0][j]=j; } for(int i=1;i<=word1.length();i++){ for(int j=1;j<=word2.length();j++){ if(word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j]=dp[i-1][j-1]; else dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1; } } return dp[word1.length()][word2.length()]; }