16-算法设计

4.4.2　算法设计

编辑距离问题满足动态规划的最优子结构性质，可以自底向上逐渐推出整体最优解。

（1）确定合适的数据结构

采用二维数组d[][]来记录编辑距离。

（2）初始化

输入两个字符串s₁、s₂，初始化d[][]第一行为0，1，2，…，len2，第一列元素为0，1，2，…，len1。

（3）循环阶段

• i=1：s₁[0]与s₂[j−1]比较，j=1，2，3，…，len2。

如果s₁[0]=s₂[j−1]，diff[i][j] = 0。

如果s₁[0] ≠s₂[j−1]，则diff[i][j] =1。

• i=2：s₁[1]与s₂[j−1]比较，j=1，2，3，…，len2。
• 以此类推，直到i >len1时，算法结束，这时d[len1][len2]就是我们要的最优解。

（4）构造最优解

从d[i][j]表格中倒推，输出插入、删除、替换了哪些字母。在此没有使用辅助数组，采用判断的方式倒推。