Levenshtein String Distance (Swift 4)

levenshtein.swift

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)