LeetCode72. 编辑距离

思路

1.定义dp数组

因为又是字符串相关问题，所以定义为i-1

dp[i][j]:表示word1中下标以i-1结尾的字符串和word2中以下标j-1结尾的字符串相等需要的最少的操作数为dp[i][j]。

2.递推公式

如果word1中下标以i-1结尾的字符和word2中下标以j-1结尾的字符相等的话，dp[i][j] = dp[i-1][j-1].说明当前的字符不需要处理。

如果不相等的话就需要处理了。分为三种情况，只处理word1，只处理word2，word1和word2一起处理。

所以dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1);

dp[i-1][j]+1就是将word1中不相等的i-1位置的字符删除掉。

dp[i][j-1]+1。就是添加一个元素在word1中。word2中删除一个元素，word1中相等于多了一个元素。

dp[i-1][j-1]+1就是直接将两者不相等的其中一个换为另一个。

3.初始化

根据定义很容易初始化的。dp[i][0] = i;dp[0][j] = j.

4.遍历dp数组

根据dp数组的定义可以知道是正序遍历。

5.打印dp数组

dp数组的最后一个元素就是最后的结果。

代码

class Solution {    public int minDistance(String word1, String word2) { int l1 = word1.length(); int l2 = word2.length(); int dp [][] = new int[l1+1][l2+1];  for(int i = 0;i<=l1;i++){     dp[i][0] = i; } for(int j = 0;j<=l2;j++){     dp[0][j] = j; } for(int i = 1;i<=l1;i++){     for(int j = 1;j<=l2;j++){  if(word1.charAt(i-1) == word2.charAt(j-1)){      dp[i][j] = dp[i-1][j-1];  }else{      dp[i][j] = Math.min(Math.min(dp[i-1][j] + 1,dp[i][j-1]+1),dp[i-1][j-1]+1);  }     } } return dp[l1][l2];    }}