当前位置:网站首页>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];
}
};
边栏推荐
- SAP UI5 框架的 manifest.json
- Leetcode hot topic Hot 100 day 32: "minimum coverage substring"
- 面试官:Redis中有序集合的内部实现方式是什么?
- C language games - minesweeping
- 2022 nurse (primary) examination questions and new nurse (primary) examination questions
- 2022 construction electrician (special type of construction work) free test questions and construction electrician (special type of construction work) certificate examination
- Design your security architecture OKR
- It's almost the new year, and my heart is lazy
- PHP online examination system version 4.0 source code computer + mobile terminal
- Math symbols in lists
猜你喜欢
Logic is a good thing
[MySQL] basic use of cursor
2022 construction electrician (special type of construction work) free test questions and construction electrician (special type of construction work) certificate examination
use. Net analysis Net talent challenge participation
[DSP] [Part 2] understand c6678 and create project
每个程序员必须掌握的常用英语词汇(建议收藏)
[diy] self designed Microsoft makecode arcade, official open source software and hardware
审稿人dis整个研究方向已经不仅仅是在审我的稿子了怎么办?
"Penalty kick" games
PHP online examination system version 4.0 source code computer + mobile terminal
随机推荐
Web开发小妙招:巧用ThreadLocal规避层层传值
Leetcode hot topic Hot 100 day 32: "minimum coverage substring"
Implementation of packaging video into MP4 format and storing it in TF Card
C language games - minesweeping
Summary of different configurations of PHP Xdebug 3 and xdebug2
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
HMS Core 机器学习服务打造同传翻译新“声”态,AI让国际交流更顺畅
Pat 1085 perfect sequence (25 points) perfect sequence
Tips for web development: skillfully use ThreadLocal to avoid layer by layer value transmission
Kubernetes learning summary (20) -- what is the relationship between kubernetes and microservices and containers?
新型数据库、多维表格平台盘点 Notion、FlowUs、Airtable、SeaTable、维格表 Vika、飞书多维表格、黑帕云、织信 Informat、语雀
The mail command is used in combination with the pipeline command statement
Huawei device command
拼多多败诉,砍价始终差0.9%一案宣判;微信内测同一手机号可注册两个账号功能;2022年度菲尔兹奖公布|极客头条
Performance test process and plan
Dynamically switch data sources
Why do novices often fail to answer questions in the programming community, and even get ridiculed?
Pat 1078 hashing (25 points) ⼆ times ⽅ exploration method
使用.Net驱动Jetson Nano的OLED显示屏
15million employees are easy to manage, and the cloud native database gaussdb makes HR office more efficient