Skip to content

Instantly share code, notes, and snippets.

@larromba
Forked from RuiNelson/Levenshtein.swift
Created March 2, 2021 19:39
Show Gist options
  • Save larromba/69c94ccea3380e87a2e99c6539cf5350 to your computer and use it in GitHub Desktop.
Save larromba/69c94ccea3380e87a2e99c6539cf5350 to your computer and use it in GitHub Desktop.
Levenshtein distance between two String for Swift 4.x
import Foundation
extension String {
subscript(index: Int) -> Character {
return self[self.index(self.startIndex, offsetBy: index)]
}
}
extension String {
public func levenshtein(_ other: String) -> Int {
let sCount = self.count
let oCount = other.count
guard sCount != 0 else {
return oCount
}
guard oCount != 0 else {
return sCount
}
let line : [Int] = Array(repeating: 0, count: oCount + 1)
var mat : [[Int]] = Array(repeating: line, count: sCount + 1)
for i in 0...sCount {
mat[i][0] = i
}
for j in 0...oCount {
mat[0][j] = j
}
for j in 1...oCount {
for i in 1...sCount {
if self[i - 1] == other[j - 1] {
mat[i][j] = mat[i - 1][j - 1] // no operation
}
else {
let del = mat[i - 1][j] + 1 // deletion
let ins = mat[i][j - 1] + 1 // insertion
let sub = mat[i - 1][j - 1] + 1 // substitution
mat[i][j] = min(min(del, ins), sub)
}
}
}
return mat[sCount][oCount]
}
}
// Access older versions (Swift 3.x) in history
// Usage:
// "abc".levenshtein("abd")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment