Use dynamic programming for Levenshtein distance.
Now it doesn't take a minute to fail to autocorrect 17 characters.
diff --git a/closest.go b/closest.go
index 14f58d5..3b51875 100644
--- a/closest.go
+++ b/closest.go
@@ -9,35 +9,33 @@
return len(s)
}
- var l1, l2, l3 int
-
- if len(s) == 1 {
- l1 = len(t) + 1
- } else {
- l1 = levenshtein(s[1:len(s)-1], t) + 1
+ dists := make([][]int, len(s)+1)
+ for i := range dists {
+ dists[i] = make([]int, len(t)+1)
+ dists[i][0] = i
}
- if len(t) == 1 {
- l2 = len(s) + 1
- } else {
- l2 = levenshtein(t[1:len(t)-1], s) + 1
+ for j := range t {
+ dists[0][j] = j
}
- l3 = levenshtein(s[1:len(s)], t[1:len(t)])
-
- if s[0] != t[0] {
- l3++
+ for i, sc := range s {
+ for j, tc := range t {
+ if sc == tc {
+ dists[i+1][j+1] = dists[i][j]
+ } else {
+ dists[i+1][j+1] = dists[i][j] + 1
+ if dists[i+1][j] < dists[i+1][j+1] {
+ dists[i+1][j+1] = dists[i+1][j] + 1
+ }
+ if dists[i][j+1] < dists[i+1][j+1] {
+ dists[i+1][j+1] = dists[i][j+1] + 1
+ }
+ }
+ }
}
- if l2 < l1 {
- l1 = l2
- }
-
- if l1 < l3 {
- return l1
- }
-
- return l3
+ return dists[len(s)][len(t)]
}
func closestChoice(cmd string, choices []string) (string, int) {
