Skip to content

Instantly share code, notes, and snippets.

@RuiNelson
Last active August 2, 2023 03:50
Show Gist options
  • Save RuiNelson/82bf91214e3e09222233b1fc04139c86 to your computer and use it in GitHub Desktop.
Save RuiNelson/82bf91214e3e09222233b1fc04139c86 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")
@alessign
Copy link

alessign commented Dec 6, 2017

Swift 4 deprecation fix:

`

private extension String {
    subscript(ix: Int) -> Character {
        let index = self.index(startIndex, offsetBy: ix)
        return self[index]
}

subscript(range: Range<Int>) -> String {
        let start = index(startIndex, offsetBy: range.lowerBound)
        let end = index(startIndex, offsetBy: range.upperBound)
        return String(self[start ..< end])
    }
}

`

@sameerjj
Copy link

Adding to above:

  • swift 4 now has direct character count
let (length, cmpLength) = (self.count, cmpString.count)

		guard cmpLength > 0 else {
			return self.count
		}

  • swift 4 need to explicitly call Swift.min
matrix[m][n] = Swift.min(horizontal, vertical, diagonal + penalty)

@RuiNelson
Copy link
Author

@sameerjj thank you, I've remade it from the ground up to Swift 4.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment