Hot 100 --- 编辑距离

本文概览本文讲解编辑距离的核心思路dp[i][j] 表示 word1 前 i 个字符转成 word2 前 j 个字符的最少操作数两个字符相等就跳过不花操作不相等就在删除、插入、替换三种手段里选最省的方法一是二维 DP方法二只保留上一行把空间降到 O(m)一、题目二、题目分析1. 题目要求给你两个单词word1和word2返回将word1转换成word2所使用的最少操作数。你可以对一个单词进行以下三种操作插入一个字符删除一个字符替换一个字符示例 1word1 horse, word2 ros→ 3horse → rorse替换 h→r→rorse → rose删除 r→rose → ros删除 e示例 2word1 intention, word2 execution→ 52. 怎么想这题先看看暴力能不能做。每一步都有三种操作可选走一步分三岔、走两步分九岔……操作数一多分支就是 3^k 级别地爆开枚举不完。这条路直接堵死。换个角度想想操作这件事到底在干什么。插入、删除、替换一次只动一个字符而且动完之后两个字符串就各自往前推进了一格。也就是说整个过程就是两个字符串一个字一个字地往前对对到哪儿、花了多少步是可以被记住的。这和上一篇《最长公共子序列》是同一个姿势两个串各自都有进度。设 word1 看到第i个字符、word2 看到第j个字符把状态定成dp[i][j] word1 的前 i 个字符 转成 word2 的前 j 个字符 需要的最少操作数要求的就是dp[n][m]两个整串。接下来只需要想清楚(i, j)这个局面怎么由更小的局面推出来。先看最简单的情况这两个位置的字符正好相等。比如 word1 的第i个字符和 word2 的第j个字符都是a。那这个a根本不用动——不用插入、不用删除、不用替换它俩天然就对上了。既然不动就等于这两个字符可以一起消掉问题直接退化成前i-1个转成前j-1个操作数一次都不花。再看不一样的。这时必须动手而手里正好有三张牌删除、插入、替换。每种牌打出去之后剩下的问题是不同的小局面——有的变成前i-1对前j有的变成前i对前j-1有的变成前i-1对前j-1。搞清楚每张牌对应哪个小局面、再取最省的那张这题就通了。3. 需要解决哪几个问题问题一两个字符不相等时删除、插入、替换这三种操作各自把问题变成了哪个更小的局面为什么问题二初值怎么填word1或word2为空串的时候是多少步问题三进阶二维表能不能压成一维数组三、方法一二维 DPO(n × m) 空间1. 思路概览publicintminDistance(Stringword1,Stringword2){intnword1.length(),mword2.length();int[][]dpnewint[n1][m1];// 初值word2 为空word1 前 i 个只能全删i 步for(inti0;in;i){dp[i][0]i;}// 初值word1 为空只能靠插入凑出 word2 前 j 个j 步for(intj0;jm;j){dp[0][j]j;}for(inti1;in;i){for(intj1;jm;j){if(word1.charAt(i-1)word2.charAt(j-1)){dp[i][j]dp[i-1][j-1];// 相等跳过不花操作}else{dp[i][j]1Math.min(Math.min(dp[i-1][j],// 删除dp[i][j-1]),// 插入dp[i-1][j-1]);// 替换}}}returndp[n][m];}思路简要说明状态定义dp[i][j] word1 前i个字符转成 word2 前j个字符的最少操作数转移字符相等 →dp[i-1][j-1]不等 →1 min(删除, 插入, 替换)初值dp[i][0] i全删、dp[0][j] j全插时间复杂度 O(n × m)空间 O(n × m)2. 思路详解第一步解决状态定义dp[i][j]处理的是两个前缀word1 的前i个字符、word2 的前j个字符。之所以用前缀而不是整串是因为每做一次操作问题都在往更短的前缀上退一路退到空串为止。答案dp[n][m]就是把前缀推到头。第二步解决转移方程情况一两个字符相等word1[i-1] word2[j-1]。这两个字符天然对得上三种操作都用不着。既然什么都不用做就相当于把它们一并从两边拿掉问题退化成前i-1个转前j-1个dp[i][j] dp[i-1][j-1]注意这里不加 1——因为这一步没花任何操作。情况二两个字符不相等。这时必须动手三种手段挨个看它把问题变成了什么。① 删除删掉 word1 的第i个字符。既然它和 word2 的第j个对不上干脆把它抹掉让它从此不再参与比较。删掉之后word1 剩下的就是前i-1个而 word2 那边一个都没少仍然要凑出前j个。所以问题变成前i-1个转前j个删除的代价 dp[i-1][j] 1那个1就是这一次删除操作本身。② 插入在 word1 的第i个字符后面插入一个和 word2 第j个字符相同的字符。这个稍微绕一点举个例子。word1 ab、word2 abcword1 的b对着 word2 的c对不上。这时候最优解是在b后面插入一个c——插入的这个c正好顶替 word2 的第 3 个字符于是 word1 这边凑齐了前 3 个而 word2 的那一位也就被消化掉了剩下要管的只是前 2 个转前 2 个。所以一次插入等于用掉 word2 的第j个字符问题变成前i个转前j-1个插入的代价 dp[i][j-1] 1③ 替换把 word1 的第i个字符改成 word2 的第j个字符。这个最直白。改完之后这两个字符就相等了——也就回到情况一这一对字符可以一起消掉。所以问题变成前i-1个转前j-1个替换的代价 dp[i-1][j-1] 1三种手段取最省dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 删 插 替三种手段能覆盖所有走法——面对一对对不上的字符无非就是不要 word1 的这个删、“不要 word2 的那个”插、“原地把它改成对方”替。所以取三者最小就不会漏最优解。第三步解决初值——空串怎么办边界就是其中一边为空的情形没法再靠转移方程推得单独定dp[i][0] iword2 是空串word1 前i个字符要变成空只能一个一个全删掉 →i步。dp[0][j] jword1 是空串要凑出 word2 的前j个字符只能一个一个全插入 →j步。这两个初值也顺带回答了dp[0][0] 0两个都是空串不用动。第四步完整执行过程以示例 1word1 horse、word2 ros答案是 3为例word2 r o s 0 1 2 3 ← 初值word1 空全插入 h 1 1 2 3 ← h!rmin(删1, 插1, 替0)1 1 o 2 2 1 2 ← oo等于 dp[1][1] 1 r 3 2 2 2 ← rr等于 dp[2][1] 2 s 4 3 3 2 ← ss等于 dp[3][2] 2 e 5 4 4 3 ← e!smin(删2, 插4, 替3)1 3挑几个格子看dp[1][1]h ! r → 1 min(dp[0][1]1, dp[1][0]1, dp[0][0]0) 1 dp[2][2]o o → dp[1][1] 1 dp[3][2]r ! o → 1 min(dp[2][2]1, dp[3][1]2, dp[2][1]2) 2 dp[4][3]s s → dp[3][2] 2 dp[5][3]e ! s → 1 min(dp[4][3]2, dp[5][2]4, dp[4][2]3) 3最后dp[5][3] 3✓。注意dp[4][3] 2那一格说明hors → ros只要 2 步把h换成r、删掉r再拿e这一格看末尾的e和s对不上删掉它 1 步就够所以最终 3 步。3. 复杂度分析时间复杂度 O(n × m)两层循环每格常数次比较。空间复杂度 O(n × m)完整二维表。四、二维表里其实只用到上一行看转移方程dp[i][j]用到的还是那三个老邻居。把表按行列摆好i是行、j是列列 j-1 列 j 行 i-1 dp[i-1][j-1] dp[i-1][j] 行 i dp[i][j-1] dp[i][j] ← 当前要算的dp[i-1][j]同一列、上一行 →正上方dp[i][j-1]同一行、上一列 →正左方dp[i-1][j-1]上一行、上一列 →左上方对角线也就是说算第i行只用到上一行整行和当前行左边一格第i-2行及更早的都用不上了。和上一篇一样可以把两行挤进同一个一维数组。滚动时有两个地方要留神对角线dp[i-1][j-1]会被覆盖要用prev提前存住还有第一列dp[i][0]每行都在变得单独更新。五、方法二一维滚动数组O(m) 空间1. 思路概览publicintminDistance(Stringword1,Stringword2){intnword1.length(),mword2.length();int[]dpnewint[m1];// 初值等价于二维表的第一行word1 为空全插入for(intj0;jm;j){dp[j]j;}for(inti1;in;i){intprevdp[0];// 对角线 dp[i-1][j-1]逐列往后挪dp[0]i;// 第一列 dp[i][0] iword2 为空全删for(intj1;jm;j){inttempdp[j];// 先存下旧值 dp[i-1][j]下一列当对角线用if(word1.charAt(i-1)word2.charAt(j-1)){dp[j]prev;}else{dp[j]1Math.min(Math.min(dp[j],dp[j-1]),prev);}prevtemp;}}returndp[m];}思路简要说明状态定义dp[j]表示当前行第j列的值随i逐行滚动初值dp[j] j正是二维表第一行每行开头dp[0] i补上第一列的边界对角线用prev提前存住否则会被覆盖时间复杂度 O(n × m)空间 O(m)2. 思路详解第一步初始化为什么是dp[j] j一维的dp对应当前行。外层i从 1 开始进循环之前dp得先装好二维表的第一行——也就是word1 为空凑 word2 前 j 个要插 j 次正好是dp[j] j。第二步为什么每行开头要写dp[0] i看二维表的第一列dp[i][0]表示word1 前 i 个转成空串答案是i全删。它是逐行变化的第 1 行是 1、第 2 行是 2……而dp[0]在滚动数组里从头到尾不进内层循环j从 1 开始如果不管它它就永远停在初值 0 上。所以每进一行得手动把它更新成当前行的值dp[0]i;这一步是这题比《最长公共子序列》多出来的地方——那题的dp[0]恒为 0不需要管这题的第一列是 1、2、3……必须自己维护。第三步prev为什么还在内层循环里dp[j]要在被覆盖前先读出它代表的东西dp[j]还没覆盖时是上一行同列的dp[i-1][j]→ 就是正上方dp[j-1]本列之前已更新是本行前一列的dp[i][j-1]→ 就是正左方而对角线dp[i-1][j-1]在算dp[j-1]时就已经被顶掉了所以要用prev提前留住它。prev的接力过程就是上一列循环里存下的temp也就是dp[i-1][j-1]在本列开头赋给prev用掉然后本列自己的旧值dp[j]又存进temp留给下一列当对角线。这一句int temp dp[j]; ... prev temp;和《最长公共子序列》里那段完全一样。注意prev的初值是dp[0]也就是dp[i-1][0] i-1——它正好是第 1 列的对角线衔接上了。第四步完整执行过程仍是word1 horse、word2 rosm3。初始dp [0, 1, 2, 3]i1 (h)prev dp[0] 0dp[0] 1 j1: temp1h!r → dp[1] 1 min(dp[1]1, dp[0]1, prev0) 1prev1 → [1,1,2,3] j2: temp2h!o → dp[2] 1 min(dp[2]2, dp[1]1, prev1) 2prev2 → [1,1,2,3] j3: temp3h!s → dp[3] 1 min(dp[3]3, dp[2]2, prev2) 3prev3 → [1,1,2,3] i2 (o)prev dp[0] 1dp[0] 2 j1: temp1o!r → dp[1] 1 min(dp[1]1, dp[0]2, prev1) 2prev1 → [2,2,2,3] j2: temp2oo → dp[2] prev 1prev2 → [2,2,1,3] j3: temp3o!s → dp[3] 1 min(dp[3]3, dp[2]1, prev2) 2prev3 → [2,2,1,2] i3 (r)prev dp[0] 2dp[0] 3 j1: temp2rr → dp[1] prev 2prev2 → [3,2,1,2] j2: temp1r!o → dp[2] 1 min(dp[2]1, dp[1]2, prev2) 2prev1 → [3,2,2,2] j3: temp2r!s → dp[3] 1 min(dp[3]2, dp[2]2, prev1) 2prev2 → [3,2,2,2] i4 (s)prev dp[0] 3dp[0] 4 j1: temp2s!r → dp[1] 1 min(dp[1]2, dp[0]4, prev3) 3prev2 → [4,3,2,2] j2: temp2s!o → dp[2] 1 min(dp[2]2, dp[1]3, prev2) 3prev2 → [4,3,3,2] j3: temp2ss → dp[3] prev 2prev2 → [4,3,3,2] i5 (e)prev dp[0] 4dp[0] 5 j1: temp3e!r → dp[1] 1 min(dp[1]3, dp[0]5, prev4) 4prev3 → [5,4,3,2] j2: temp3e!o → dp[2] 1 min(dp[2]3, dp[1]4, prev3) 4prev3 → [5,4,4,2] j3: temp2e!s → dp[3] 1 min(dp[3]2, dp[2]4, prev3) 3prev2 → [5,4,4,3] 返回 dp[3] 3 ✓每一轮结束时的dp正好等于二维表里对应的那一行方法一逐行结果 dp 滚动结果 [0, 1, 2, 3]第一行→ [0, 1, 2, 3] [1, 1, 2, 3]h 行 → [1, 1, 2, 3] [2, 2, 1, 2]o 行 → [2, 2, 1, 2] [3, 2, 2, 2]r 行 → [3, 2, 2, 2] [4, 3, 3, 2]s 行 → [4, 3, 3, 2] [5, 4, 4, 3]e 行 → [5, 4, 4, 3]看i2的j2o o用的是prev 1也就是对角线的旧值得 1要是错读成已经被覆盖的dp[1]就会算错。3. 复杂度分析时间复杂度 O(n × m)循环规模不变。空间复杂度 O(m)只留一行从 O(n × m) 降到 O(m)。六、总结维度方法一 二维 DP方法二 一维滚动状态dp[i][j]两个前缀dp[j]只保留当前行相等时dp[i-1][j-1]不花操作取prev不等时1 min(上方, 左方, 对角线)1 min(dp[j], dp[j-1], prev)每行要做两件事——dp[0] iprev 旧 dp[0]空间O(n × m)O(m)这道题的转移方程不用背它就是从一次操作到底改了什么推出来的字符相等→ 天然对上不用动直接把这一对消掉dp[i-1][j-1]不加 1。字符不等→ 三种手段各对应一个更小的局面删除 word1 的第i个 → 它不再参与 → 前i-1对前j即dp[i-1][j]插入一个字符顶替 word2 的第j个 → 用掉了这一位 → 前i对前j-1即dp[i][j-1]替换 word1 的第i个成对方 → 变成相等一起消掉 → 前i-1对前j-1即dp[i-1][j-1]。三种手段穷尽了所有走法取最小就是最优。把这套dp[i][j]填成二维表后发现只用得到上一行再用prev把对角线救下来就压成了一维——比上一篇多做的一件事情是第一列dp[i][0]每行都在变得自己用dp[0] i维护。