How to edit distance in leetcode dynamic programming with golang

This article mainly introduces how to edit the distance of golang leetcode dynamic programming. It is very detailed and has a certain reference value. Friends who are interested must read it!

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:

Input: word1 = "horse", word2 = "ros" output: 3 explanation: horse-> rorse (replace'h' with'r') rorse-> rose (delete'r') rose-> ros (delete'e')

Example 2:

Input: 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')

Ideas for solving the problem:

The editing distance, also known as levenshtein distance, is used to measure the similarity of two strings, assuming that the two strings are word1 and word2, respectively, using m [I] [j] to store the editing distance of word1 [0word2], word2 [0word2] (left closed and right open), for I, and j position editing distance m [IQ1] [jig1]

1, if word1 [I] = = word2 [j], the editing distance is

The editing distance of m [I] [j], word1 [0 I], word2 [0RJ] (left closed and right open)

The editing distance of word2 [0:j+1] (left closed and right open)

The editing distance of C 0:i+1 m [item1] [j] + 1 Magi word 1 [0:i+1], word2 [0 rig j] (left closed and right open)

The least in these three cases

2, if word1 [I]! = word2 [j], the editing distance is

In the above three branches, An is replaced by m [I] [j] + 1

3, because m [I + 1] [jacks 1] uses m [I] [jacks 1], m [icycles 1] [j], m [I] [j], so the incremental cycle is adopted.

4. Initial conditions. In order to facilitate initialization, we have an optimization technique here: add a space before word1 and word2, then:

A _ ~ m [0] [0] = 0

Bhopal m [I] [0] = I

Cm [0] [j] = j

Func minDistance (word1 string, word2 string) int {if word1== "" {return len (word2)} if word2== "" {return len (word1)} m:=make ([] [] int,len (word1) + 1) for iPlus "