Levenshtein distance between strings (Swift)

String+LevenhsteinDistance.swift

import Foundation

// Based on: https://gist.github.com/kyro38/50102a47937e9896e4f4
// (Updated to Swift 5, formatted to follow Swift conventions and fixed bug with empty strings)

extension String {
    /// Levenshtein distance between strings.
    static func levenshteinDistance(_ x: String, _ y: String) -> Int {
        let xArray = Array(x.utf16)
        let yArray = Array(y.utf16)
        
        var dist = Array2D(columnCount: xArray.count + 1, rowCount: yArray.count + 1)
        
        for i in 1 ..< xArray.count + 1 {
            dist[i, 0] = i
        }
        
        for j in 1 ..< yArray.count + 1 {
            dist[0, j] = j
        }
        
        for i in 1 ..< xArray.count + 1 {
            for j in 1 ..< yArray.count + 1 {
                if xArray[i - 1] == yArray[j - 1] {
                    dist[i, j] = dist[i - 1, j - 1]  // noop
                    
                } else {
                    dist[i, j] = [
                        dist[i - 1, j] + 1,  // deletion
                        dist[i, j - 1] + 1,  // insertion
                        dist[i - 1, j - 1] + 1  // substitution
                    ].min()!
                }
            }
        }
        
        return dist[xArray.count, yArray.count]
    }
    
    struct Array2D {
        let columnCount: Int
        let rowCount: Int
        var elements: [Int]
        
        init(columnCount: Int, rowCount: Int) {
            self.columnCount = columnCount
            self.rowCount = rowCount
            
            self.elements = Array(repeating: 0, count: columnCount * rowCount)
        }
        
        subscript(column: Int, row:Int) -> Int {
            get {
                return elements[self.columnCount * row + column]
            }
            set {
                elements[self.columnCount * row + column] = newValue
            }
        }
    }
    
}

extension String {
    /// Basic tests
    static func testLevenshteinDistance() {
        print()
        print("[Testing String.levenshteinDistance]")
        
        let pairs = [
            ("here", ""),
            ("", "there"),
            ("here", "there"),
            ("kitten", "sitten"),
            ("sitten", "sittin"),
            ("sittin", "sitting"),
        ]
        
        for pair in pairs {
            let (x, y) = pair
            let distance = String.levenshteinDistance(x, y)
            let percent = (Double(distance) / Double([x.count, y.count].max()!) * 100).rounded()
            print("'\(x)' -> '\(y)' => distance=\(distance) (\(percent)%)")
        }
        
        print()
    }
}