描述 Description

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:

a) Insert a character
b) Delete a character
c) Replace a character

[Edit Distance]

分析 Analysis

X 和Y 的编辑距离 ed(X[m], Y[n]) 定义为：从字符串strings X转换到 Y 需要的插入、删除、替换两个相邻的基本单位(字符)的最小个数。即编辑距离是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。

假设字符串 a, 共 m 位，从 a[1] 到 a[m]
字符串 b, 共 n 位，从 b[1] 到 b[n]
d[i][j] 表示字符串 a[1]-a[i] 转换为 b[1]-b[j] 的编辑距离。

那么有如下递归规律（a[i] 和 b[j] 分别是当前要计算编辑距离的子字符串 a 和 b 的最后一位）：

1. 当 a[i] 等于 b[j] 时，d[i][j] = d[i-1][j-1], 比如 fxy -> fay 的编辑距离等于 fx -> fa 的编辑距离
2. 当 a[i] 不等于 b[j] 时，d[i][j] 等于如下 3 项的最小值：
   • d[i-1][j] + 1（删除 a[i]（删除等价于插入操作，相当于插入b中插入a[i[）），比如 fxy -> fab 的编辑距离 = fx -> fab 的编辑距离 + 1
   • d[i][j-1] + 1（删除b[j]或者插入b[j])，比如 fxy -> fab 的编辑距离 = fxyb -> fab 的编辑距离 + 1 = fxy -> fa 的编辑距离 + 1
   • d[i-1][j-1] + 1（将a[i]b[j]同时删除（等价于交换操作）），比如 fxy -> fab 的编辑距离 = fxb -> fab 的编辑距离 + 1 = fx -> fa 的编辑距离 + 1

递归边界：

1. a[i][0] = i, b 字符串为空，表示将 a[1]-a[i] 全部删除，所以编辑距离为 i
2. a[0][j] = j, a 字符串为空，表示 a 插入 b[1]-b[j]，所以编辑距离为 j

示例

例如以字符串 a = "fxy", b = "fab" 为例：

1. 首先建立一个矩阵，用来存放子问题及原问题的编辑距离，并将递归边界在矩阵中填好，如下：

   

2. 然后计算 i = 1, j = 1 所对应的编辑距离：比较 a[i] 和 b[j] 是否相等然后根据递归规律算出这个值
   比如在这种情况下 a[i] = f 和 b[j] = f, 那么 d[i][j] 就等于 d[i-1][j-1] 等于 0
   然后计算 i = 1, j = 2 直到算出 i = 3, j = 3, 原问题的编辑距离就等于 d[3][3]
   最终矩阵如下：

   

即要计算d[i][j]只需要知道3个位置上的值。

例如以字符串 a = "fxy", b = "fab" 为例：

1. 首先建立一个矩阵，用来存放子问题及原问题的编辑距离，并将递归边界在矩阵中填好，如下：

   

2. 然后计算 i = 1, j = 1 所对应的编辑距离：比较 a[i] 和 b[j] 是否相等然后根据递归规律算出这个值
   比如在这种情况下 a[i] = f 和 b[j] = f, 那么 d[i][j] 就等于 d[i-1][j-1] 等于 0
   然后计算 i = 1, j = 2 直到算出 i = 3, j = 3, 原问题的编辑距离就等于 d[3][3]
   最终矩阵如下：

   

即要计算d[i][j]只需要知道3个位置上的值。

复杂度分析

时间复杂度为 O(mn)。

空间复杂度可以写成 O(min(m,n))。

代码 Code

#include <iostream>

using namespace std;

int minDistance(string word1, string word2) {
    int l1 = (int) word1.length();
    int l2 = (int) word2.length();
    int minl = l1 < l2 ? l1 : l2;
    int maxl = l1 > l2 ? l1 : l2;
    string longs, shorts;
    if (maxl == l1) {
        longs = word1;
        shorts = word2;
    } else {
        longs = word2;
        shorts = word1;
    }

    int *dist = new int[minl + 1];
    for (int j = 0; j <= minl; j++)
        dist[j] = j;

    int tmp, old; //old = 没有修改过的dist[j-1]
    for (int i = 1; i <= maxl; i++) { //对长字符串迭代
        dist[0] = i;
        old = i - 1;
        for (int j = 1; j <= minl; j++) { //对短字符串迭代
            tmp = dist[j];
            if (longs[i - 1] == shorts[j - 1])
                dist[j] = old;
            else
                dist[j] = min(dist[j] + 1, min(old + 1, dist[j - 1] + 1));
            old = tmp;
        }
    }
    return dist[minl];
}