EditDistanceDP is an optimised implementation which builds on the ideas of the recursive implementation. We use dynamic programming to compute the DP table where dp[i][j] denotes the edit distance value of first[0..i-1] and second[0..j-1]. Time complexity is O(m * n) where m and n are lengths of the
(first string, second string)
| 35 | // of first[0..i-1] and second[0..j-1]. Time complexity is O(m * n) where m and n are lengths of the strings, |
| 36 | // first and second respectively. |
| 37 | func EditDistanceDP(first string, second string) int { |
| 38 | |
| 39 | m := len(first) |
| 40 | n := len(second) |
| 41 | |
| 42 | // Create the DP table |
| 43 | dp := make([][]int, m+1) |
| 44 | for i := 0; i <= m; i++ { |
| 45 | dp[i] = make([]int, n+1) |
| 46 | } |
| 47 | |
| 48 | for i := 0; i <= m; i++ { |
| 49 | for j := 0; j <= n; j++ { |
| 50 | |
| 51 | if i == 0 { |
| 52 | dp[i][j] = j |
| 53 | continue |
| 54 | } |
| 55 | |
| 56 | if j == 0 { |
| 57 | dp[i][j] = i |
| 58 | continue |
| 59 | } |
| 60 | |
| 61 | if first[i-1] == second[j-1] { |
| 62 | dp[i][j] = dp[i-1][j-1] |
| 63 | continue |
| 64 | } |
| 65 | |
| 66 | dp[i][j] = 1 + min.Int(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) |
| 67 | } |
| 68 | } |
| 69 | |
| 70 | return dp[m][n] |
| 71 | } |