编辑距离问题

参考《labuladong的算法小抄》

问题描述

如果可以对一个字符串进行三种操作：插入一个字符，删除一个字符，替换一个字符。
现在给你两个字符串s1和s2，求最少需要多少次操作可以把s1转换成s2。

思路分析

解决两个字符串的问题，都可以用两个指针i和j分别只想两个字符串的最后，一步一步往前移动，以缩小问题规模
根据实际情况进行字符的插入，删除，替换以及适当地skip

if s1[i] == s2[j]:
    #啥都别做（skip）

    #同时两个指针向前移动
else:
    #insert
    #delete
    #replace

代码示例

def minDistance(s1, s2) -> int:
    def dp(i, j) -> int: #定义dp(i, j)为s1[0...i]和s2[0...j]的最小编辑距离
        #base case
        if i == -1: return j+1
        if j == -1: return i+1

        #做选择
        if s1[i] == s2[j]:
            return dp(i - 1, j - 1) #相等就不用操作，所以不用加一直接前进
        else:
            return min(
                dp(i, j - 1) + 1,
                #插入
                #直接在s1[i]中插入一个和s2[j]一样的字符
                #那么s2[j]就被匹配了，前移j，继续和i做对比
                #别忘了操作数加一

                dp(i - 1, j) + 1,
                #删除
                #直接把s1[i]这个字符删除
                #前移i，继续和j对比
                #别忘了操作数加一

                dp(i - 1, j - 1) + 1
                #替换
                #直接把s1[i]替换成s2[j]，这样它俩就匹配了
                #同时前移i，j继续做对比
                #别忘了操作数加一
            )

    return dp(len(s1) - 1, len(s2) - 1)

使用DP table进行重叠子问题优化

这是个一个DP table

	..	a	p	p
..	0	1	2	3
r	1	1	2	3
a	2	1	2	3
d	3	2	2	3

虽然dp数组与dp函数的含义相同，但是DP table是自底向上求解，递归解法是自顶向下求解

int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m+1][n+1];

    //base case
    for(int i = 1; i <= m; i++)
        dp[i][0] = i;
    for(int j = 1; j <= n; j++)
        dp[0][j] = j;
    
    //自底向上求解
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++) 
            if(s1.charAt(i-1) == s2.charAt(j-1))
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = min(
                    dp[i-1][j] + 1,
                    dp[i][j-1] + 1,
                    dp[i-1][j-1] + 1
                );
    //储存整个s1和s2的最小编辑距离
    return dp[m][n];
}

int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
}

如果需要记录操作，则可以把int[][] dp升级成Node[][] dp

/*
choice：
    0 什么都不做
    1 插入
    2 删除
    3 替换
*/

class Node {
    int val; // 记录操作次数
    int choice; // 记录这一步的操作是什么

    Node(int val, int choice) {
        this.val = val;
        this.choice = choice;
    }
}

Node minNode(Node a, Node b, Node c) {
    Node res = new Node(a.val, 2);

    if(res.val > b.val) {
        res.val = b.val;
        res.choice = 1;
    }
    if(res.val > c.val) {
        res.val = c.val;
        res.choice = 3;
    }

    return res;
}

int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    Node[][] dp = new Node[m+1][n+1];

    //base case
    for(int i = 1; i <= m; i++)
        dp[i][0] = new Node(i, 2);
    for(int j = 1; j <= n; j++)
        dp[0][j] = new Node(j, 1);
    
    //自底向上求解
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++) 
            if(s1.charAt(i-1) == s2.charAt(j-1))
                Node node = dp[i-1][j-1];
                dp[i][j] = new Node(node.val, 0);
            else
                dp[i][j] = minNode(
                    dp[i-1][j],
                    dp[i][j-1],
                    dp[i-1][j-1]
                );
                dp[i][j].val++;
    //储存整个s1和s2的最小编辑距离并打印
    return dp[m][n].val;
}