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. class Solution {
  4. public:
  5.     int minDistance(const string &word1, const string &word2) {
  6.         const size_t n = word1.size();
  7.         const size_t m = word2.size();
  8.         // 长度为n的字符串，有n+1个隔板
  9.         int f[n + 1][m + 1];
  10.         for (size_t i = 0; i <= n; i++)
  11.             f[i][0] = i;
  12.         for (size_t j = 0; j <= m; j++)
  13.             f[0][j] = j;
  15.         for (size_t i = 1; i <= n; i++) {
  16.             for (size_t j = 1; j <= m; j++) {
  17.                 if (word1[i - 1] == word2[j - 1])
  18.                     f[i][j] = f[i - 1][j - 1];
  19.                 else {
  20.                     int mn = min(f[i - 1][j], f[i][j - 1]);
  21.                     f[i][j] = 1 + min(f[i - 1][j - 1], mn);
  22.                 }
  23.             }
  24.         }
  25.         return f[n][m];
  26.     }
  27. };

动规+滚动数组

  1. // Edit Distance
  2. // 二维动规+滚动数组
  3. // 时间复杂度O(n*m)，空间复杂度O(n)
  4. class Solution {
  5. public:
  6.     int minDistance(const string &word1, const string &word2) {
  7.         if (word1.length() < word2.length())
  8.             return minDistance(word2, word1);
  10.         int f[word2.length() + 1];
  11.         int upper_left = 0; // 额外用一个变量记录f[i-1][j-1]
  13.         for (size_t i = 0; i <= word2.size(); ++i)
  14.             f[i] = i;
  16.         for (size_t i = 1; i <= word1.size(); ++i) {
  17.             upper_left = f[0];
  18.             f[0] = i;
  20.             for (size_t j = 1; j <= word2.size(); ++j) {
  21.                 int upper = f[j];
  23.                 if (word1[i - 1] == word2[j - 1])
  24.                     f[j] = upper_left;
  25.                 else
  26.                     f[j] = 1 + min(upper_left, min(f[j], f[j - 1]));
  28.                 upper_left = upper;
  29.             }
  30.         }
  32.         return f[word2.length()];
  33.     }
  34. };

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