编辑距离 图解题解

编辑距离这道题在问什么

给两个单词 word1 和 word2，每一步可以对 word1 插入、删除或替换一个字符，问把 word1 完全变成 word2 最少要几步。比如把 horse 变成 ros 只需 3 步。难点在于操作序列的自由度太大：先删哪个、在哪插、要不要替换，组合起来是天文数字，逐一枚举操作序列不可行。

为什么想到用两个前缀做状态

换个视角，别盯着操作序列，盯着两个字符串的末尾。想把 word1 的前 i 个字符变成 word2 的前 j 个字符，最优方案里对最后一个位置的处理只有四种可能：两个末位字符本来就相同，直接对上、不花操作；或者删掉 word1 的末字符；或者在末尾插入 word2 的末字符；或者把 word1 的末字符替换成 word2 的末字符。

无论选哪种，剩下的部分都是一个更短前缀对更短前缀的同样问题。也就是说，「word1 前 i 位变 word2 前 j 位的最少步数」只依赖三个更小的子问题，与前面具体怎么变过来的无关——这就是无后效性，二维动态规划的地基。

dp 表怎么定义，首行首列为什么是 0 到 n

定义 dp[i][j] 为把 word1 的前 i 个字符变成 word2 的前 j 个字符的最少操作数，答案就是右下角 dp[m][n]。表比字符串各多一行一列，用来表达空串。

边界先铺好：dp[0][j] = j，空串要变出长度 j 的前缀，只能一个个插入，恰好 j 步；dp[i][0] = i，要把长度 i 的前缀变成空串，只能一个个删光。左上角 dp[0][0] = 0，空串变空串不用动。忘了这两条边界是本题最常见的错误，后面每一格都建立在它们之上。

三条来路为什么分别对应删、插、替换

填内部格 dp[i][j] 时，先比较 word1 第 i 个字符和 word2 第 j 个字符。相同时这一对天然对上，dp[i][j] = dp[i-1][j-1]，直接抄左上角，一步不花——注意相同时不能加一，多加就把答案算大了。

不同时三选一取最小再加一：dp[i-1][j] + 1 是删——先把 word1 少末位的前缀变好，再删掉这个多余字符；dp[i][j-1] + 1 是插——先变出 word2 少末位的前缀，再补插上它的末字符；dp[i-1][j-1] + 1 是替换——两边各退一位先对齐，再把这对不同的字符换掉。三条路覆盖了处理末位的全部方式，取最小者即最优，方向别记混：上是删、左是插、左上是替换。

复杂度多少，空间怎么优化

时间复杂度 O(m·n)，m、n 是两个单词的长度：整张表每格填一次，每次只做常数次比较。空间 O(m·n) 存全表；由于每格只依赖上一行和本行左边，可用滚动数组只保留一行、再拿一个变量暂存左上角值，空间降到 O(n)。

编辑距离（也叫 Levenshtein 距离）是拼写纠错、DNA 序列比对、模糊搜索的底层度量，这张「前缀对前缀」的二维表也是最长公共子序列等一整族双串动态规划的通用骨架，值得吃透。

Python

def minDistance(w1, w2):
    m, n = len(w1), len(w2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for j in range(n+1): dp[0][j] = j
    for i in range(m+1): dp[i][0] = i
    for i in range(1, m+1):
        for j in range(1, n+1):
            if w1[i-1] == w2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

C++

int minDistance(string w1, string w2){
    int m = w1.size(), n = w2.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for(int j=0;j<=n;j++) dp[0][j]=j;
    for(int i=0;i<=m;i++) dp[i][0]=i;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(w1[i-1]==w2[j-1]) dp[i][j]=dp[i-1][j-1];
            else dp[i][j]=1+min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]});
    return dp[m][n];
}

Java

int minDistance(String w1, String w2){
    int m = w1.length(), n = w2.length();
    int[][] dp = new int[m+1][n+1];
    for(int j=0;j<=n;j++) dp[0][j]=j;
    for(int i=0;i<=m;i++) dp[i][0]=i;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(w1.charAt(i-1)==w2.charAt(j-1)) dp[i][j]=dp[i-1][j-1];
            else dp[i][j]=1+Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
    return dp[m][n];
}