Skip to content

Instantly share code, notes, and snippets.

@automactic
Created January 17, 2018 22:13
Show Gist options
  • Save automactic/f8e1d26c3c23ddbc5b8c2151f119d663 to your computer and use it in GitHub Desktop.
Save automactic/f8e1d26c3c23ddbc5b8c2151f119d663 to your computer and use it in GitHub Desktop.
Levenshtein distance in swift 4
class Levenshtein {
private(set) var cache = [Set<String.SubSequence>: Int]()
func calculateDistance(a: String.SubSequence, b: String.SubSequence) -> Int {
let key = Set([a, b])
if let distance = cache[key] {
return distance
} else {
let distance: Int = {
if a.count == 0 || b.count == 0 {
return abs(a.count - b.count)
} else if a.first == b.first {
return calculateDistance(a: a[a.index(after: a.startIndex)...], b: b[b.index(after: b.startIndex)...])
} else {
let add = calculateDistance(a: a, b: b[b.index(after: b.startIndex)...])
let replace = calculateDistance(a: a[a.index(after: a.startIndex)...], b: b[b.index(after: b.startIndex)...])
let delete = calculateDistance(a: a[a.index(after: a.startIndex)...], b: b)
return min(add, replace, delete) + 1
}
}()
cache[key] = distance
return distance
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment