'cat'(기준) 과 'cake' 의 최소 편집 거리를 구해보자.
c 와 cak 사이의 거리를 구해보자
3가지 중 가장 작은 수는 왼쪽(1) 이므로 c와 cak 사이의 거리는 1+1 = 2 이다.
func editDistance(from a: String, to b: String) -> Int {
let m = a.count
let n = b.count
var matrix = [[Int]](repeating: [Int](repeating: 0, count: n + 1), count: m + 1)
// '⌀ - 나머지 문자' 사이의 거리를 구한다.
for index in 1...m {
matrix[index][0] = index
}
// '나머지 문자 - ⌀' 사이의 거리를 구한다.
for index in 1...n {
matrix[0][index] = index
}
// 본격적으로 최소 편집 거리를 구한다.
for (i, selfChar) in a.enumerated() {
for (j, otherChar) in b.enumerated() {
if otherChar == selfChar {
// 동일한 문자 사이의 거리는 왼쪽 위 거리와 같다.
matrix[i + 1][j + 1] = matrix[i][j]
} else {
// 서로 다른 문자 사이의 거리는 왼쪽, 왼쪽위, 위쪽 중 최소값 + 1 이다.
matrix[i + 1][j + 1] = min(matrix[i][j] + 1, matrix[i + 1][j] + 1, matrix[i][j + 1] + 1)
}
}
}
return matrix[m][n]
}
출처 : https://blog.naver.com/ndb796/220870218783 (안경잡이개발자)