Lexi's Leetcode solutions

Posts Tagged ‘2WayDP

将一个字符串变成另外一个字符串所用的最少操作数,每次只能增加、删除或者替换一个字符。如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];