EditDistanceRecursive is a naive implementation with exponential time complexity.
(first string, second string, pointerFirst int, pointerSecond int)
| 10 | |
| 11 | // EditDistanceRecursive is a naive implementation with exponential time complexity. |
| 12 | func EditDistanceRecursive(first string, second string, pointerFirst int, pointerSecond int) int { |
| 13 | |
| 14 | if pointerFirst == 0 { |
| 15 | return pointerSecond |
| 16 | } |
| 17 | |
| 18 | if pointerSecond == 0 { |
| 19 | return pointerFirst |
| 20 | } |
| 21 | |
| 22 | // Characters match, so we recur for the remaining portions |
| 23 | if first[pointerFirst-1] == second[pointerSecond-1] { |
| 24 | return EditDistanceRecursive(first, second, pointerFirst-1, pointerSecond-1) |
| 25 | } |
| 26 | |
| 27 | // We have three choices, all with cost of 1 unit |
| 28 | return 1 + min.Int(EditDistanceRecursive(first, second, pointerFirst, pointerSecond-1), // Insert |
| 29 | EditDistanceRecursive(first, second, pointerFirst-1, pointerSecond), // Delete |
| 30 | EditDistanceRecursive(first, second, pointerFirst-1, pointerSecond-1)) // Replace |
| 31 | } |
| 32 | |
| 33 | // EditDistanceDP is an optimised implementation which builds on the ideas of the recursive implementation. |
| 34 | // We use dynamic programming to compute the DP table where dp[i][j] denotes the edit distance value |