【动态规划】用全C站最简单易懂的语言讲明白编辑距离问题

编辑距离问题!是动态规划问题中看似困难实际上确实也没那么简单的一道题,但一旦掌握了思想,代码的书写就会变得万分简单,这次博主将会用全C站最为简单易懂的语言——中国话,来向大家好好讲解一下这道题。

在这里插入图片描述

牛客链接

题目描述

给定两个单词word1word2,请计算将word1转换为word2至少需要多少步操作。
你可以对一个单词执行以下3种操作:
a)在单词中插入一个字符
b)删除单词中的一个字符
c)替换单词中的一个字符

示例:

word1 :“a”

word2:“c”

返回值1

方法有三(考虑最简单操作):

  1. 先将word1中的字符a删除,然后插入字符c,两步操作
  2. 先向word1中插入字符c,然后删除字符a,两步操作
  3. 直接将word1中的字符a替换成字符c,一步操作

思路分析

想要知晓word1整体转换成word2整体所花费的最少的操作,可以循序渐进,先求word1字符串的局部转换为word2的局部所花费的最少操作,在此基础上,进行一步转移操作,或是插入或是删除或是替换,选择其中操作步数最少的一种选项来一步步逼近最后的结果

如果将word1的前i个字符转换成word2的前j个字符,所需要的编辑距离设置为状态F(i,j),那么想要获取F(i,j)的值,可以由F(i,j-1)F(i-1,j)F(i-1,j-1)三种状态一步转移获得。

  • F(i,j-1)转移至F(i,j),意思是已经知道word1的前i个字符转移成word2的前j-1个字符最小编辑距离为F(i,j-1),可是现在想要的更多,想要将word1的前i个字符转换成word2的前j个字符,那么只有将word2的第j个字符插入到word1中方能实现
  • F(i-1,j)转移至F(i,j),意思是已经知道word1的前i-1个字符转移成word2的前j个字符最小编辑距离为F(i-1,j),想要求F(i,j),那么只能将word1中多余的第i个字符删除
  • F(i-1,j-1)转移至F(i,j),意思是已经知道word1的前i-1个字符转移成word2的前j-1个字符最小编辑距离为F(i-1,j-1),想要求F(i,j),就需要判断word1的第i个字符和word2的第j个字符是否相同,如果相同,那么就不需要进行任何的操作,F(i,j)等于F(i-1,j-1),如果不相等,就需要将word1的第i个字符替换成word2的第j个字符

综上所述,

动态规划四角度:

  1. 状态定义F(i,j):word1的前i个字符转换成word2的前j个字符,所需要的编辑距离

  2. 状态间的转移方程定义F(i,j):min(插入,删除,替换或无操作)

    min(F(i,j-1),F(i-1,j),F(i-1,j-1)+(word1[i] == word2[j] ? 0:1))(这里word1[i]和word2[j]中的i和j指的是第i个字符,第j个字符,并非下标索引)

  3. 状态的初始化F(i,0)= i, F(0,j)= j

(前者意思是将word1中前i个字符都转换成空串,获取最小的编辑距离只能有几个字符就删除几个字符;后者道理相同,将一个空串转换成word2前j个字符,获取最小的编辑距离只能是缺几个字符就插入几个字符)

  1. 返回结果F(word1.length(),word2.length())

图例展示

示例:

word1:as

word2:ears

在这里插入图片描述

代码展示

import java.util.*;
public class Solution {
    public int minDistance (String word1, String word2) {
        int row = word1.length(); //word1的长度
        int col = word2.length(); //word2的长度
        int[][] ret = new int[row + 1][col + 1]; //存放状态的数组
        //第一列初始化
        for(int i = 0;i <= row ;i++) {
            ret[i][0] = i;
        }
        //第一行初始化
        for(int j = 1;j <= col;j++) {
            ret[0][j] = j;
        }
        for(int i = 1;i <= row ;i++) {
            for(int j = 1;j <= col;j++) {
                if(word1.charAt(i-1) == word2.charAt(j-1)) {
                    ret[i][j] = ret[i-1][j-1];  //如果word1的第i个字符和word2的第j个字符相同,不需要进行任何操作
                }else {
                    ret[i][j] = Math.min(ret[i][j-1]+1,ret[i-1][j]+1); //插入和删除操作中选操作数较少的
                    ret[i][j] = Math.min(ret[i][j],ret[i-1][j-1] + 1); //上面的结果和替换操作中选编辑数小的
                }   
            }
        }
        return ret[row][col]; //返回结果
    }
}

完!

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇

)">
下一篇>>