Skip to content

Instantly share code, notes, and snippets.

@natecook1000
Last active October 2, 2019 04:21
Show Gist options
  • Save natecook1000/add0e5ce654bab231987 to your computer and use it in GitHub Desktop.
Save natecook1000/add0e5ce654bab231987 to your computer and use it in GitHub Desktop.
Memoized Levenshtein Distance
// memoized Levenshtein Distance
// description given here: http://programmingpraxis.com/2014/09/12/levenshtein-distance/
// memoize for a two parameter recursive function
func memoize<T1: Hashable, T2: Hashable, U>(_ body: @escaping (@escaping (T1, T2) -> U) -> (T1, T2) -> U) -> ((T1, T2) -> U) {
var memo = [T1: [T2: U]]()
var result: ((T1, T2) -> U)!
result = { value1, value2 in
if let cached = memo[value1]?[value2] { return cached }
let toCache = body(result)(value1, value2)
memo[value1, default: [:]][value2] = toCache
return toCache
}
return result
}
func __levenshteinDistance(_ step: @escaping(Substring, Substring) -> Int) -> (Substring, Substring) -> Int {
return { s1, s2 in
if s1.isEmpty { return s2.count }
if s2.isEmpty { return s1.count }
// drop first letter of each string
let s1Crop = s1.dropFirst()
let s2Crop = s2.dropFirst()
// if first characters are equal, continue with both cropped
if s1.first == s2.first {
return step(s1Crop, s2Crop)
}
// otherwise find smallest of the three options
let (c1, c2, c3) = (step(s1Crop, s2), step(s1, s2Crop), step(s1Crop, s2Crop))
return 1 + min(c1, c2, c3)
}
}
let _levenshteinDistance = memoize(__levenshteinDistance)
extension StringProtocol where Self.SubSequence == Substring {
func levenshteinDistance<S>(from other: S) -> Int
where S: StringProtocol, S.SubSequence == Substring
{
return _levenshteinDistance(self[...], other[...])
}
}
"hill".levenshteinDistance(from: "hilt")
"Apple Watch".levenshteinDistance(from: "Watch")
"🐣🐥🐤🐔".levenshteinDistance(from: "🐔🐣🐥🐤")
// 1, 6, 2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment