字符串编辑距离：计算最小操作数

/**
* 首先用0填充attrs[i][j]，生成距离存储集合
* 先将最大距离填充到行首和列首
* 如果s[i-1]==t[j-1]则编辑距离不需要增加，editAttrs[i][j]==editAttrs[i-1][j-1]
* 如果二者不相等，则取前面三种编辑方式中最小距离加1,因为只需要在上一步最优方式中操作一次(增加/删除/补空)就可以
* editAttrs[i][j] = min(editAttrs[i-1][j-1],editAttrs[i][j-1],editAttrs[i-1][j])
*/
fun minStepForEdit(sourceStr: String, targerStr: String): Int {
var stepCount = 0
var editAttrs = mutableListOf<MutableList>()
println(sourceStr)
println(targerStr)

// 如果i从sourceStr开始，则下方双for循环也需要从sourceStr开始
// 如果i从targetStr开始，则下方双for循环也需要从targetStr开始
// 这二者对应就可以
for (i in 0..targerStr.length) {
var tempMulti = mutableListOf()
for (j in 0..sourceStr.length) {
tempMulti.add(0)
}
editAttrs.add(tempMulti)
}
for (i in 0..targerStr.length) {
editAttrs[i][0] = i
}
for (i in 0..sourceStr.length) {
editAttrs[0][i] = i
}
for (i in 1..targerStr.length) {
for (j in 1..sourceStr.length) {
if (targerStr[i-1].equals(sourceStr[j-1])) {
editAttrs[i][j] = editAttrs[i-1][j-1]
} else {
var count = if (editAttrs[i][j-1]>editAttrs[i-1][j]) {
if (editAttrs[i-1][j-1]<editAttrs[i-1][j]) {
editAttrs[i-1][j-1] + 1
} else {
editAttrs[i-1][j] + 1
}
} else {
if (editAttrs[i-1][j-1]<editAttrs[i][j-1]) {
editAttrs[i-1][j-1] + 1
} else {
editAttrs[i][j-1] + 1
}
}
editAttrs[i][j] = count
}
}
}
stepCount = editAttrs[targerStr.length][sourceStr.length]
editAttrs.forEach {
var values = it
values.forEach {
print(it)
print(” “)
}
println()
}
return stepCount
}