Created
February 16, 2018 13:46
-
-
Save fabio914/6f02629c99f5f2c254f8350a8afcd546 to your computer and use it in GitHub Desktop.
Levenshtein String Distance (Swift 4)
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 | |
| struct Matrix<T> { | |
| let columns: Int | |
| let rows: Int | |
| private var matrix: [T] | |
| init(columns: Int, rows: Int, repeating: T) { | |
| self.columns = columns | |
| self.rows = rows | |
| matrix = Array(repeating: repeating, count: columns * rows) | |
| } | |
| subscript(column: Int, row: Int) -> T { | |
| get { | |
| return matrix[columns * row + column] | |
| } | |
| set { | |
| matrix[columns * row + column] = newValue | |
| } | |
| } | |
| } | |
| func levenshtein(_ first: String, _ second: String) -> Int { | |
| let firstArray = Array(first.unicodeScalars) | |
| let secondArray = Array(second.unicodeScalars) | |
| let firstLength = firstArray.count | |
| let secondLength = secondArray.count | |
| if firstLength == 0 { return secondLength } | |
| else if secondLength == 0 { return firstLength } | |
| var distance = Matrix(columns: firstLength + 1, rows: secondLength + 1, repeating: 0) | |
| for i in 1...firstLength { distance[i, 0] = i } | |
| for j in 1...secondLength { distance[0, j] = j } | |
| for i in 1...firstLength { | |
| for j in 1...secondLength { | |
| let cost = firstArray[i - 1] == secondArray[j - 1] ? 0:1 | |
| distance[i, j] = min(distance[i - 1, j] + 1, distance[i, j - 1] + 1, distance[i - 1, j - 1] + cost) | |
| } | |
| } | |
| return distance[firstLength, secondLength] | |
| } | |
| extension String { | |
| func levenshteinDistance(to other: String) -> Int { | |
| return levenshtein(self, other) | |
| } | |
| } | |
| // Tests: | |
| print("".levenshteinDistance(to: "") == 0) | |
| print("".levenshteinDistance(to: "a") == 1) | |
| print("a".levenshteinDistance(to: "a") == 0) | |
| print("A".levenshteinDistance(to: "a") == 1) | |
| print("abc".levenshteinDistance(to: "abc") == 0) | |
| print("Abc".levenshteinDistance(to: "abc") == 1) | |
| print("acb".levenshteinDistance(to: "abc") == 2) | |
| print("kitten".levenshteinDistance(to: "sitting") == 3) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment