Scott Baker | 1fe7273 | 2019-10-21 10:58:51 -0700 | [diff] [blame] | 1 | package flags |
| 2 | |
| 3 | func levenshtein(s string, t string) int { |
| 4 | if len(s) == 0 { |
| 5 | return len(t) |
| 6 | } |
| 7 | |
| 8 | if len(t) == 0 { |
| 9 | return len(s) |
| 10 | } |
| 11 | |
| 12 | dists := make([][]int, len(s)+1) |
| 13 | for i := range dists { |
| 14 | dists[i] = make([]int, len(t)+1) |
| 15 | dists[i][0] = i |
| 16 | } |
| 17 | |
| 18 | for j := range t { |
| 19 | dists[0][j] = j |
| 20 | } |
| 21 | |
| 22 | for i, sc := range s { |
| 23 | for j, tc := range t { |
| 24 | if sc == tc { |
| 25 | dists[i+1][j+1] = dists[i][j] |
| 26 | } else { |
| 27 | dists[i+1][j+1] = dists[i][j] + 1 |
| 28 | if dists[i+1][j] < dists[i+1][j+1] { |
| 29 | dists[i+1][j+1] = dists[i+1][j] + 1 |
| 30 | } |
| 31 | if dists[i][j+1] < dists[i+1][j+1] { |
| 32 | dists[i+1][j+1] = dists[i][j+1] + 1 |
| 33 | } |
| 34 | } |
| 35 | } |
| 36 | } |
| 37 | |
| 38 | return dists[len(s)][len(t)] |
| 39 | } |
| 40 | |
| 41 | func closestChoice(cmd string, choices []string) (string, int) { |
| 42 | if len(choices) == 0 { |
| 43 | return "", 0 |
| 44 | } |
| 45 | |
| 46 | mincmd := -1 |
| 47 | mindist := -1 |
| 48 | |
| 49 | for i, c := range choices { |
| 50 | l := levenshtein(cmd, c) |
| 51 | |
| 52 | if mincmd < 0 || l < mindist { |
| 53 | mindist = l |
| 54 | mincmd = i |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | return choices[mincmd], mindist |
| 59 | } |