Edit Distance

描述

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:

  • Insert a character
  • Delete a character
  • Replace a character

    分析

设状态为f[i][j]，表示A[0,i]和B[0,j]之间的最小编辑距离。设A[0,i]的形式是str1c，B[0,j]的形式是str2d，

  • 如果c==d，则f[i][j]=f[i-1][j-1]；

  • 如果c!=d，

    • 如果将c替换成d，则f[i][j]=f[i-1][j-1]+1；
    • 如果在c后面添加一个d，则f[i][j]=f[i][j-1]+1；
    • 如果将c删除，则f[i][j]=f[i-1][j]+1；

      动规

  1. // Edit Distance
  2. // 二维动规，时间复杂度O(n*m)，空间复杂度O(n*m)
  3. public class Solution {
  4.     public int minDistance(String word1, String word2) {
  5.         final int n = word1.length();
  6.         final int m = word2.length();
  7.         // 长度为n的字符串，有n+1个隔板
  8.         int[][] f = new int[n+1][m+1];
  9.         for (int i = 0; i <= n; i++)
  10.             f[i][0] = i;
  11.         for (int j = 0; j <= m; j++)
  12.             f[0][j] = j;
  14.         for (int i = 1; i <= n; i++) {
  15.             for (int j = 1; j <= m; j++) {
  16.                 if (word1.charAt(i - 1) == word2.charAt(j - 1))
  17.                     f[i][j] = f[i - 1][j - 1];
  18.                 else {
  19.                     int mn = Math.min(f[i - 1][j], f[i][j - 1]);
  20.                     f[i][j] = 1 + Math.min(f[i - 1][j - 1], mn);
  21.                 }
  22.             }
  23.         }
  24.         return f[n][m];
  25.     }
  26. }

动规+滚动数组

  1. // Edit Distance
  2. // 二维动规+滚动数组
  3. // 时间复杂度O(n*m)，空间复杂度O(n)
  4. public class Solution {
  5.     public int minDistance(String word1, String word2) {
  6.         if (word1.length() < word2.length())
  7.             return minDistance(word2, word1);
  9.         int[] f = new int[word2.length() + 1];
  10.         int upper_left = 0; // 额外用一个变量记录f[i-1][j-1]
  12.         for (int i = 0; i <= word2.length(); ++i)
  13.             f[i] = i;
  15.         for (int i = 1; i <= word1.length(); ++i) {
  16.             upper_left = f[0];
  17.             f[0] = i;
  19.             for (int j = 1; j <= word2.length(); ++j) {
  20.                 int upper = f[j];
  22.                 if (word1.charAt(i - 1) == word2.charAt(j - 1))
  23.                     f[j] = upper_left;
  24.                 else
  25.                     f[j] = 1 + Math.min(upper_left, Math.min(f[j], f[j - 1]));
  27.                 upper_left = upper;
  28.             }
  29.         }
  31.         return f[word2.length()];
  32.     }
  33. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/dp/edit-distance.html