当前位置:网站首页>968 edit distance
968 edit distance
2022-07-06 21:01:00 【-Lin Zeyu】
The title is as follows
Here are two words for you word1 and word2, Please return to word1 convert to word2 The minimum number of operands used .
You can do the following three operations on a word :
Insert a character
Delete a character
Replace a character
Example 1:
Input :word1 = “horse”, word2 = “ros”
Output :3
explain :
horse -> rorse ( take ‘h’ Replace with ‘r’)
rorse -> rose ( Delete ‘r’)
rose -> ros ( Delete ‘e’)
Example 2:
Input :word1 = “intention”, word2 = “execution”
Output :5
explain :
intention -> inention ( Delete ‘t’)
inention -> enention ( take ‘i’ Replace with ‘e’)
enention -> exention ( take ‘n’ Replace with ‘x’)
exention -> exection ( take ‘n’ Replace with ‘c’)
exection -> execution ( Insert ‘u’)
Tips :
0 <= word1.length, word2.length <= 500
word1 and word2 It's made up of lowercase letters
Their thinking
Dynamic programming
We can do three operations on any word :
Insert a character ;
Delete a character ;
Replace a character .
The title is given two words , Set to A and B, In this way, we can six operation methods .
But we can see , If we have words A And the words B:
Pairs of words A Delete a character and pair words B Inserting a character is equivalent . For example, when the word A by doge, word B by dog when , We can delete words A Last character of e, Get the same dog, You can also use words B Add a character at the end e, Get the same doge;
Empathy , Pairs of words B Delete a character and pair words A Inserting a character is also equivalent ;
Pairs of words A Replace a character and pair words B Replacing a character is equivalent . For example, when the word A by bat, word B by cat when , We modify words A First letter of b -> c, And modify words B First letter of c -> b It is equivalent. .
Since then , There are actually only three different operations :
In the word A Insert a character in ;
In the word B Insert a character in ;
Modify the word A A character of .
Since then , We can turn the original problem into a smaller subproblem . We use it A = horse,B = ros As an example , Let's take a look at how to transform this problem into several smaller sub problems .
In the word A Insert a character in : If we knew horse To ro The editing distance of is a, So clearly horse To ros Your editing distance will not exceed a + 1. This is because we can a After this operation, it will horse and ro Become the same string , Only additional 1 operations , In the word A Add characters at the end of s, You can be in a + 1 After this operation, it will horse and ro Become the same string ;
In the word B Insert a character in : If we knew hors To ros The editing distance of is b, So clearly horse To ros Your editing distance will not exceed b + 1, The reason as above ;
Modify the word A A character of : If we knew hors To ro The editing distance of is c, So clearly horse To ros Your editing distance will not exceed c + 1, The reason as above .
So from horse become ros The editing distance should be min(a + 1, b + 1, c + 1).
Be careful : Why are we always talking about words A and B Insert or modify characters at the end of , Can it be operated in other places ? The answer is yes , But we know that , The sequence of operations does not affect the final result . For example, for words cat, We hope that c and a Add characters between d And put the character t Change to character b, Then the two operations are in whatever order , Will get the final result cdab.
You may think horse To ro This problem is also difficult to solve . But it doesn't matter , We can continue to use the above method to split this problem , For all sub problems of this problem , We can also continue to split , until :
character string A It's empty , If you follow The switch to ro, Obviously, the edit distance is a string B The length of , Here is 2;
character string B It's empty , If you follow horse The switch to , Obviously, the edit distance is a string A The length of , Here is 5.
therefore , We can use dynamic programming to solve this problem . We use it D[i][j] Express A Before i Letters and B Before j The edit distance between letters .
As mentioned above , When we get D[i][j-1],D[i-1][j] and D[i-1][j-1] After that, we can calculate D[i][j].
D[i][j-1] by A Before i Characters and B Before j - 1 Sub problem of character editing distance . That is for B Of the j Characters , We are A The same character is added at the end of the , that D[i][j] The minimum can be D[i][j-1] + 1;
D[i-1][j] by A Before i - 1 Characters and B Before j Sub problem of character editing distance . That is for A Of the i Characters , We are B The same character is added at the end of the , that D[i][j] The minimum can be D[i-1][j] + 1;
D[i-1][j-1] by A front i - 1 Characters and B Before j - 1 Sub problem of character editing distance . That is for B Of the j Characters , We modify A Of the i Two characters make them the same , that D[i][j] The minimum can be D[i-1][j-1] + 1. Specially , If A Of the i Characters and B Of the j The two characters are the same , Then we don't actually need to modify . under these circumstances ,D[i][j] The minimum can be D[i-1][j-1].
Then we can write the following state transition equation :
So the results of each step will be based on the results of the previous step , It is shown as follows :
For boundary cases , The edit distance between an empty string and a non empty string is D[i][0] = i and D[0][j] = j,D[i][0] It's equivalent to word1 perform i Delete operations ,D[0][j] It's equivalent to word1 perform j Insert operations .
To sum up, we get the whole process of the algorithm .
Solution code
class Solution
{
public:
int minDistance(string word1, string word2)
{
int n = word1.length();
int m = word2.length();
// There is a string that is empty
if (n * m == 0) return n + m;
// DP Array
vector<vector<int>> D(n + 1, vector<int>(m + 1));
// Boundary state initialization
for (int i = 0; i < n + 1; i++)
{
D[i][0] = i;
}
for (int j = 0; j < m + 1; j++)
{
D[0][j] = j;
}
// Calculate all DP value
for (int i = 1; i < n + 1; i++)
{
for (int j = 1; j < m + 1; j++)
{
int left = D[i - 1][j] + 1;
int down = D[i][j - 1] + 1;
int left_down = D[i - 1][j - 1];
if (word1[i - 1] != word2[j - 1]) left_down += 1;
D[i][j] = min(left, min(down, left_down));
}
}
return D[n][m];
}
};
边栏推荐
- What key progress has been made in deep learning in 2021?
- [DSP] [Part 2] understand c6678 and create project
- 知识图谱之实体对齐二
- Statistical inference: maximum likelihood estimation, Bayesian estimation and variance deviation decomposition
- Summary of different configurations of PHP Xdebug 3 and xdebug2
- Opencv learning example code 3.2.3 image binarization
- [DIY]自己设计微软MakeCode街机,官方开源软硬件
- Performance test process and plan
- PHP saves session data to MySQL database
- Mtcnn face detection
猜你喜欢
Manifest of SAP ui5 framework json
Application layer of tcp/ip protocol cluster
Swagger UI tutorial API document artifact
请问sql group by 语句问题
[DSP] [Part 2] understand c6678 and create project
全网最全的知识库管理工具综合评测和推荐:FlowUs、Baklib、简道云、ONES Wiki 、PingCode、Seed、MeBox、亿方云、智米云、搜阅云、天翎
Spark SQL chasing Wife Series (initial understanding)
Distributed ID
硬件开发笔记(十): 硬件开发基本流程,制作一个USB转RS232的模块(九):创建CH340G/MAX232封装库sop-16并关联原理图元器件
Design your security architecture OKR
随机推荐
Common doubts about the introduction of APS by enterprises
Mécanisme de fonctionnement et de mise à jour de [Widget Wechat]
OneNote 深度评测:使用资源、插件、模版
C language games - minesweeping
Simple continuous viewing PTA
[DSP] [Part 2] understand c6678 and create project
OSPF多区域配置
Regular expression collection
审稿人dis整个研究方向已经不仅仅是在审我的稿子了怎么办?
正则表达式收集
Recyclerview GridLayout bisects the middle blank area
Logic is a good thing
[MySQL] trigger
7. Data permission annotation
Core principles of video games
What are RDB and AOF
The most comprehensive new database in the whole network, multidimensional table platform inventory note, flowus, airtable, seatable, Vig table Vika, flying Book Multidimensional table, heipayun, Zhix
Activiti global process monitors activitieventlistener to monitor different types of events, which is very convenient without configuring task monitoring in acitivit
Database - how to get familiar with hundreds of tables of the project -navicat these unique skills, have you got it? (exclusive experience)
华为设备命令