levenshteinDistance calculates the edit distance between two strings
(s1, s2 string)
| 82 | |
| 83 | // levenshteinDistance calculates the edit distance between two strings |
| 84 | func levenshteinDistance(s1, s2 string) int { |
| 85 | len1 := len(s1) |
| 86 | len2 := len(s2) |
| 87 | |
| 88 | // Create a 2D slice for dynamic programming |
| 89 | matrix := make([][]int, len1+1) |
| 90 | for i := range matrix { |
| 91 | matrix[i] = make([]int, len2+1) |
| 92 | } |
| 93 | |
| 94 | // Initialize first row and column |
| 95 | for i := 0; i <= len1; i++ { |
| 96 | matrix[i][0] = i |
| 97 | } |
| 98 | for j := 0; j <= len2; j++ { |
| 99 | matrix[0][j] = j |
| 100 | } |
| 101 | |
| 102 | // Fill in the rest of the matrix |
| 103 | for i := 1; i <= len1; i++ { |
| 104 | for j := 1; j <= len2; j++ { |
| 105 | cost := 0 |
| 106 | if s1[i-1] != s2[j-1] { |
| 107 | cost = 1 |
| 108 | } |
| 109 | |
| 110 | matrix[i][j] = min( |
| 111 | matrix[i-1][j]+1, // deletion |
| 112 | matrix[i][j-1]+1, // insertion |
| 113 | matrix[i-1][j-1]+cost, // substitution |
| 114 | ) |
| 115 | } |
| 116 | } |
| 117 | |
| 118 | return matrix[len1][len2] |
| 119 | } |
| 120 | |
| 121 | func min(a, b, c int) int { |
| 122 | if a < b { |