Lexi's Leetcode solutions

将一个字符串变成另外一个字符串所用的最少操作数，每次只能增加、删除或者替换一个字符。如lamb -> slave

这是经典二维DP题。希望做完这个能掌握二维dp要领，因为实在是不够直观。

思路

1. 状态：d[i][j]表示将A的0~i这个substring转化成b的0~j这个substring要的最少次数。
2. 所以在二维递归的时候，我们一直有三个已经算好的值：（假设 i = m, j = v，即想算lam->slav)
   • d[i-1][j-1]: A, B不算当前char，把A转成B最少要几步 (la -> sla)
   • d[i-1][j]: A不算当前char，转成B最少要几步 (la -> slav)
   • d[i][j – 1]: A转成B比当前char少一个，最少要几步 (lam -> sla)
3. 这样的话，怎么由介三个推d[i][j]呢？
   •  (la -> sla)已经算好了，所以看m和v是不是同一个字符，是的话，直接d[i][j]就=d[i-1][j-1]；不是的话，相当于替换第m成v，lam就能变成slav了，即步数+1。
   • (la -> slav)已经算好，所以现在处理lam怎么办呢？删一个m成la就行了，因为已经知道怎么把la变成slav了。即步数+1。
   • (lam -> sla)已经算好，所以后面加一个v就行了，lamv就能变成slav了，即步数+1。
4. 二维dp一定要先写出来已经有什么了，并且有的这三个东西的物理意义。这种求最小的，肯定是dp的，就别花时间自我怀疑了。

int minDistance(String word1, String word2) {
 int[][] d = new int[word1.length()][word2.length()];
 boolean hadSameInA = false;
 boolean hadSameInB = false;
 if (word1.charAt(0) == word2.charAt(0)) {
 d[0][0] = 0;
 hadSameInA = true;
 hadSameInB = true;
 } else {
 d[0][0] = 1;
 }
//do the same for string B. 但是别人做的都是直接assign i,不考虑有相同的情况。那是怎么回事？

 for (int i = 1; i < word1.length(); i++) {
  for (int j = 1; j < word2.length(); j++) {
  if (word1.charAt(i) == word2.charAt(j))
   d[i][j] = d[i - 1][j - 1];
  else {
   d[i][j] = Math.min(d[i - 1][j - 1] + 1, Math.min(d[i][j - 1] + 1, d[i - 1][j] + 1));
 }
return d[word1.length - 1][word2.length - 1];