前言
今天是10月的最后一天，把10月没写的博客给补上。
正文
问题来源
最近在看etcd相关的源码，其中该源码用到cobra框架，看cobra的时候看到了编辑距离这个算法。以前在笔试的时候遇到过这个问题，当时也没有怎么认真的对待，今天就好好看看。
问题描述
两个单词之间的编辑距离（Levenshtein distance）是将一个单词更改为另一个单词所需的单字符编辑（插入，删除或替换）的最小次数。
示例
举个栗子，将eeba转变成abac：
① eba（删除第一个e）
② aba（将剩下的e替换成a）
③ abac（在末尾插入c）
所以eeba和abac的编辑距离就是3
分析：
详细请看维基百科Levenshtein distance
状态转移方程：
lev(i-1,j-1) Sa[i] == Sb[j]
lev(i,j)=
min(lev(i-1,j-1),lev(i-1,j),lev(i,j-1)) Sa[i] != Sb[j]
Sa,Sb为两字符串
Cobra中的算法：
// ld compares two strings and returns the levenshtein distance between them.
func ld(s, t string, ignoreCase bool) int {
if ignoreCase {
s = strings.ToLower(s)
t = strings.ToLower(t)
}
d := make([][]int, len(s)+1)
for i := range d {
d[i] = make([]int, len(t)+1)
}
for i := range d {
d[i][0] = i
}
for j := range d[0] {
d[0][j] = j
}
for j := 1; j <= len(t); j++ {
for i := 1; i <= len(s); i++ {
if s[i-1] == t[j-1] {
d[i][j] = d[i-1][j-1]
} else {
min := d[i-1][j]
if d[i][j-1] < min {
min = d[i][j-1]
}
if d[i-1][j-1] < min {
min = d[i-1][j-1]
}
d[i][j] = min + 1
}
}
}
return d[len(s)][len(t)]
}
该算法用在检查用户输入的命令不存在时，返回相类似的命令。
总结：
多看源码，增长见识
结语
不要懒，多看多写。
