标签搜索

目 录CONTENT

文章目录

编辑距离.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 8 阅读 / 5,196 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

编辑距离

@[toc]

一、问题描述

给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符

示例 1:

输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

方法一:动态规划

解决两个字符串的动态规划问题, ⼀般都是⽤两个指针 i,j 分别指向两个字符串的最后, 然后⼀步步往前⾛, 缩⼩问题的规模

设两个字符串分别为 "rad" 和 "apple", 为了把 s1 变成 s2 , 算法会这样进⾏:
在这里插入图片描述

我们还可以发现操作不只有三个, 其实还有第四个操作:
就是什么都不要做(skip) 。 ⽐如这个情况:

在这里插入图片描述

因为这两个字符本来就相同, 为了使编辑距离最⼩, 显然不应该对它们有任何操作, 直接往前移动 i,j 即可。

还有⼀个很容易处理的情况, 就是 j ⾛完 s2 时, 如果 i 还没⾛完s1 , 那么只能⽤删除操作把 s1 缩短为 s2 。 ⽐如这个情况:

在这里插入图片描述

类似的, 如果 i ⾛完 s1 时 j 还没⾛完了 s2 , 那就只能⽤插⼊操作把s2 剩下的字符全部插⼊ s1 。

详解:
对于每对⼉字符 s1[i] 和 s2[j] , 可以有四种操作:

if s1[i] == s2[j]:
	啥都别做(skip)
	i, j 同时向前移动
else:
	三选⼀:
		插⼊(insert)
		删除(delete)
		替换(replace)

有这个框架, 问题就已经解决了。 读者也许会问, 这个「三选⼀」 到底该怎么选择呢? 很简单, 全试⼀遍, 哪个操作最后得到的编辑距离最⼩, 就选谁。 这⾥需要递归技巧, 理解需要点技巧, 先看下代码:

def minDistance(s1, s2) -> int:
	def dp(i, 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, # 插⼊
				dp(i - 1, j) + 1, # 删除
				dp(i - 1, j - 1) + 1 # 替换
			)
		# i, j 初始化指向最后⼀个索引
	return dp(len(s1) - 1, len(s2) - 1)

解释:

递归出口是 i ⾛完 s1 或 j ⾛完 s2 , 可以直接返回另⼀个字符串剩下的⻓度(因为要么是删除要么是插入)

我们这⾥ dp(i, j) 函数的定义是这样的:

def dp(i, j) -> int
# 返回 s1[0..i] 和 s2[0..j] 的最⼩编辑距离

记住这个定义之后, 先来看这段代码:

if s1[i] == s2[j]:
	return dp(i - 1, j - 1) # 啥都不做
# 解释:
# 本来就相等, 不需要任何操作
# s1[0..i] 和 s2[0..j] 的最⼩编辑距离等于
# s1[0..i-1] 和 s2[0..j-1] 的最⼩编辑距离
# 也就是说 dp(i, j) 等于 dp(i-1, j-1)

如果 s1[i]! =s2[j] , 就要对三个操作递归了, 稍微需要点思考:

dp(i, j - 1) + 1, # 插⼊
# 解释:
# 我直接在 s1[i] 插⼊⼀个和 s2[j] ⼀样的字符
# 那么 s2[j] 就被匹配了, 前移 j, 继续跟 i 对⽐
# 别忘了操作数加⼀

对于删除:

dp(i - 1, j) + 1, # 删除
# 解释:
# 我直接把 s[i] 这个字符删掉
# 前移 i, 继续跟 j 对⽐
# 操作数加⼀

对于替换:

dp(i - 1, j - 1) + 1 # 替换
# 解释:
# 我直接把 s1[i] 替换成 s2[j], 这样它俩就匹配了
# 同时前移 i, j 继续对⽐
# 操作数加

本⽂算法的递归框架:

def dp(i, j):
	dp(i - 1, j - 1) #1
	dp(i, j - 1) #2
	dp(i - 1, j) #3

对于⼦问题 dp(i-1, j-1) , 如何通过原问题 dp(i, j) 得到呢? 有不⽌⼀条路径, ⽐如 dp(i, j) -> #1 和 dp(i, j) -> #2 -> #3 。

⼀旦发现⼀条重复路径, 就说明存在巨量重复路径, 也就是重叠⼦问题

完整代码(超时):

class Solution {
public:
    int dp(string word1,string word2,int i,int j)
    {
        //规定 i 用来遍历word1, j 用来遍历word2,如果有 i 或者 j 小于0,代表其遍历当字符串已经走完,直接返回对方字符串剩下的字符串长度(要么是删除,要么是插入,加上所需的次数即可)
       if(i < 0)
       {
           return j + 1;
       }

       if(j < 0)
       {
           return i + 1;
       }

        //如果i和j对应位置的字符相等,不用任何操作,直接返回继续比较下一个字符
       if(word1[i] == word2[j])
       {
           return dp(word1,word2,i-1,j-1);
       }
       else
       {
           //如果i和j对应位置的字符不想等,就返回删除、替换、插入三种所需要的操作数的最小值,详细博客中国年有介绍
           int Min = min(dp(word1,word2,i,j-1) + 1,
           dp(word1,word2,i-1,j) + 1);
           Min = min(Min,dp(word1,word2,i-1,j-1) + 1);
           return Min;
       }
    }
    int minDistance(string word1, string word2) {
        //当word1和word2有任意一个为空时,直接返回对方当长度,因为要么是删除,要么是插入,操作的次数都是对方当长度
         if(word1.empty())
        {
            return word2.size();
        }

        if(word2.empty())
        {
            return word1.size();
        }

        return dp(word1,word2,word1.size() - 1,word2.size() - 1);
    }
};

方法二:动规优化(待备忘录或者DP table)

备忘录:

def minDistance(s1, s2) -> int:
	memo = dict() # 备忘录
	def dp(i, j):
		if (i, j) in memo:
			return memo[(i, j)]
		...
		if s1[i] == s2[j]:
			memo[(i, j)] = ...
		else:
			memo[(i, j)] = ...
	return memo[(i, j)]
return dp(len(s1) - 1, len(s2) - 1)

完整代码:

class Solution {
public:
    int dp(string& word1,string& word2,int**& ret,int i,int j)
    {
        //规定 i 用来遍历word1, j 用来遍历word2,如果有 i 或者 j 小于0,代表其遍历当字符串已经走完,直接返回对方字符串剩下的字符串长度(要么是删除,要么是插入,加上所需的次数即可)
       if(i < 0)
       {
           return j + 1;
       }

       if(j < 0)
       {
           return i + 1;
       }

        if(ret[i][j] != -2)
        {
            return ret[i][j];
        }
        //如果i和j对应位置的字符相等,不用任何操作,直接返回继续比较下一个字符
       if(word1[i] == word2[j])
       {
           ret[i][j] = dp(word1,word2,ret,i-1,j-1);
       }
       else
       {
           //如果i和j对应位置的字符不想等,就返回删除、替换、插入三种所需要的操作数的最小值,详细博客中国年有介绍
           int Min = min(dp(word1,word2,ret,i,j-1) + 1,
           dp(word1,word2,ret,i-1,j) + 1);
           Min = min(Min,dp(word1,word2,ret,i-1,j-1) + 1);
           ret[i][j] = Min;
       }
       return ret[i][j];
    }
    int minDistance(string word1, string word2) {
        //当word1和word2有任意一个为空时,直接返回对方当长度,因为要么是删除,要么是插入,操作的次数都是对方当长度
         if(word1.empty())
        {
            return word2.size();
        }

        if(word2.empty())
        {
            return word1.size();
        }

        int Max = max(word1.size(),word2.size());//定义一个二维数组记录重复的计算

        //ret[i][j]代表下标在 i 和 j 处的编辑距离
        int **ret = (int**)malloc(sizeof(int*) * Max);

        for(int i = 0;i < Max;i++)  
        ret[i]=(int*)malloc(sizeof(int) * Max);

        //初始化为-2
        for(int i = 0;i < Max;i++)
        {
            for(int j = 0;j < Max;j++)
            {
                ret[i][j] = -2;
            }
        }

        return dp(word1,word2,ret,word1.size() - 1,word2.size() - 1);
    }
};

DP table:

⾸先明确 dp 数组的含义, dp 数组是⼀个⼆维数组, ⻓这样:
在这里插入图片描述

def dp(i, j) -> int
# 返回 s1[0..i] 和 s2[0..j] 的最⼩编辑距离
dp[i-1][j-1]
# 存储 s1[0..i] 和 s2[0..j] 的最⼩编辑距离

完整代码:

class Solution {
public:
    int Min(int a, int b, int c)
    {
        return min(a, min(b, c));
    }
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        int** dp = (int**)malloc(sizeof(int*) * m);
        for(int i = 0;i < m;i++)
        {
            dp[i] = (int*)malloc(sizeof(int) * n);
        }

        // base case,根据博客中的DP table 那张图,dp[i][0]] = i 或者 dp[0][j] = j 代表当两个字符串其中一个为空时,直接返回对应当长度(还是那句话,当其中一个字符串为空 或 者其中一个字符串先一步遍历结束时,直接返回对方字符串剩下长度,因为此时要么是删除,要么是插入,都会增加相应的次数)
        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++)
				
				//注意下标,i和j是从1开始当,而字符串是从0开始当
                //如果对应字符s1.[i-1] == s2.[j-1]相等时,没有增加次数,直接等于dp[i - 1][j - 1]
                if (s1.[i-1] == s2.[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
                    );
                // dp储存着整个 s1 和 s2 的最⼩编辑距离
        return dp[m][n];
    }
    
};

总结:

⼀般来说, 处理两个字符串的动态规划问题, 都是按本⽂的思路处理, 建⽴DP table。
为什么呢, 因为易于找出状态转移的关系, ⽐如编辑距离的 DP table:
在这里插入图片描述

  • 还有⼀个细节, 既然每个 dp[i][j] 只和它附近的三个状态有关, 空间复杂度是可以压缩成 $O(min(M, N))$ 的(M, N是两个字符串的⻓度) 。 不难, 但是可解释性⼤⼤降低, 读者可以⾃⼰尝试优化
  • 你可能还会问, 这⾥只求出了最⼩的编辑距离, 那具体的操作是什么? , 只有⼀个最⼩编辑距离肯定不够,
    还得知道具体怎么修改才⾏。这个其实很简单, 代码稍加修改, 给 dp 数组增加额外的信息即可:
// int[][] dp;
Node[][] dp;
class Node {
	int val;
	int choice;
// 0 代表啥都不做
// 1 代表插⼊
// 2 代表删除
// 3 代表替换
}

val 属性就是之前的 dp 数组的数值, choice 属性代表操作。 在做最优选择时, 顺便把操作记录下来, 然后就从结果反推具体操作。我们的最终结果不是 dp[m][n] 吗, 这⾥的 val 存着最⼩编辑距离, choice 存着最后⼀个操作, ⽐如说是插⼊操作, 那么就可以左移⼀格:
在这里插入图片描述
在这里插入图片描述

0

评论区