Last active
August 2, 2023 03:50
-
-
Save RuiNelson/82bf91214e3e09222233b1fc04139c86 to your computer and use it in GitHub Desktop.
Levenshtein distance between two String for Swift 4.x
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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") |
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)
@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
Swift 4 deprecation fix:
`
`