Calculate the Levenshtein-Distance between two Strings in Swift

Levenshtein.swift

extension String {

    subscript(index: Int) -> Character {
        return self[startIndex.advancedBy(index)]
    }

    subscript(range: Range<Int>) -> String {
        let start = startIndex.advancedBy(range.startIndex)
        let end = startIndex.advancedBy(range.endIndex)
        return self[start..<end]
    }
}

extension String {

    func levenshtein(cmpString: String) -> Int {
        let (length, cmpLength) = (characters.count, cmpString.characters.count)
        var matrix = Array(
            count: cmpLength + 1,
            repeatedValue: Array(
                count: length + 1,
                repeatedValue: 0
            )
        )

        for var m = 1; m <= cmpLength; m++ {
            matrix[m][0] = matrix[m - 1][0] + 1
        }

        for var n = 1; n <= length; n++ {
            matrix[0][n] = matrix[0][n - 1] + 1
        }

        for m in Range(start: 1, end: cmpLength + 1) {
            for n in Range(start: 1, end: length + 1) {
                let penalty = self[n - 1] == cmpString[m - 1] ? 0 : 1
                let (horizontal, vertical, diagonal) = (matrix[m - 1][n] + 1, matrix[m][n - 1] + 1, matrix[m - 1][n - 1])
                matrix[m][n] = min(horizontal, vertical, diagonal + penalty)
            }
        }

        return matrix[cmpLength][length]
    }
}

let reference = "Hello World"
assert(reference.levenshtein("Helo Wordl") == 3)
assert(reference.levenshtein("") == reference.characters.count)

Thanks for sharing! I updated the for loops to meet Swift 3 requirements and made the other String helper extensions private to focus the scope. https://gist.github.com/adamyanalunas/69f6601fad6040686d300a1cdc20f500

Hi, I updated your code for Swift 3.1, thanks.