Shulou(Shulou.com)06/02 Report--

This article will explain in detail how to achieve the minimum editing distance in programming development. The editor thinks it is very practical, so I share it with you as a reference. I hope you can get something after reading this article.

Topic description:

Given the two words word1 and word2, calculate the minimum Operand used to convert word1 to word2.

You can do the following three actions on a word:

Insert a character

Delete a character

Replace a character

Example 1:

Enter: word1 = "horse", word2 = "ros"

Output: 3

Explanation:

Horse-> rorse (replace'h' with'r')

Rorse-> rose (delete'r')

Rose-> ros (delete'e')

Example 2:

Enter: word1 = "intention", word2 = "execution"

Output: 5

Explanation:

Intention-> inention (delete't')

Inention-> enention (replace'i' with'e')

Enention-> exention (replace'n 'with' x')

Exention-> exection (replace'n 'with' c')

Exection-> execution (insert'u')

#-*-coding: utf-8-*-class Solution: "" from word1- > word2, for each character of word1, you can insert, delete, and replace. When we encounter this problem, we should first think that this is a problem that can be solved by dynamic programming, because we want to solve an optimal value from a complex problem, and this complex problem can be decomposed into multiple sub-problems. For example, if we have found the minimum editing distance from word1 [:-1] to word2, it will be much easier to calculate the editing distance for word1- > word2. Now that dynamic programming is known to be used, the problem solving step of dynamic programming is to find out the state transition equation first, and then initialize the state, assuming that dp [I] [j] represents the minimum editing distance required to word1 [: I]-> word2 [: j], then when we know DP [I-1] [jmur1] If DP [I] [j] is required, there can be the following two situations: 1. Word1 [Imur1] = = word2 [j-1]: in this case, we don't need to do anything on Word1 [I-1]. Equivalent to dp [I-1] [jmur1] that is: dp [I] [j] = DP [I-1] [jmurf 1] 2. Word1 [imur1]! = word2 [jmur1]: at this time, we have to think that we have used a two-dimensional state matrix to save the optimal value in different cases, and we should find a way to find the optimal value of the current state by using the known optimal value. A) deletion because we know that word1 [: I-1] [j] represents the minimum editing distance of word1 [: I-1]-> word2 [: J]. If we first delete word1 [: I-1]-> word2 [: J], and then delete word1 [I-1], then we can implement word1 [: I]-> word2 [: J]. Therefore, dp [I] [j] = dp [I-1] [j] + 1 B) insert because we know word1 [: I] [j-1], which represents the minimum editing distance of word1 [: I]-> word2 [: J-1]. If we first put word1 [: I]-> word2 [: J-1], and then add Word2 [j-1] after word1 [: I], then we can achieve Word2 [: I]-> word2 [: J]. Therefore, dp [I] [j] = dp [I] [j-1] + 1 c) replace because we know DP [I-1] [j-1], which represents the minimum editing distance of word1 [: I-1]-> word2 [: J-1]. If we first replace word1 [: I-1]-> word2 [: J-1], and then replace word1 [I] with word2 [j] Then you can implement word1 [: I]-> word2 [: J]. Then you can also implement word1 [: I]-> word2 [: J]. Therefore, dp [I] [j] = dp [I-1] [j-1] + 1 above a) b) c) is feasible, and what we need is the minimum editing distance. Therefore, it is necessary to choose the smallest "" def minDistance (self, word1: str) from the above three operations. Word2: str)-> int: rows = len (word1) cols = len (word2) # initialization state matrix dp = [[0] * cols for _ in range (rows)] for i in range (cols): dp [0] [I] = i for j in range (rows): dp [j] [0] = j # update for i in range according to the state transition equation (1 Rows): for j in range (1, cols): if word1 [I-1] = = word2 [j-1]: dp [I] [j] = dp [I-1] [j-1] else: dp [I] [j] = 1 + min (DP [I-1] [j], dp [I] [j-1]) Dp [I-1] [j-1]) # the last state of dynamic planning is the result we need. Return dp [- 1] [- 1] on "how to achieve minimum editing distance in programming development" is here. Hope that the above content can be helpful to you, so that you can learn more knowledge, if you think the article is good, please share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.