import UIKit
import Darwin

extension String {

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

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

extension String {

    func levenshtein(cmpString: String) -> Int {

        let (length, cmpLength) = (count(self), count(cmpString))
        let subArray = Array<Int>(count: length + 1, repeatedValue: 0)
        var matrix = Array<[Int]>(count: cmpLength + 1, repeatedValue: subArray)

        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
                matrix[m][n] = min(matrix[m - 1][n] + 1, matrix[m][n - 1] + 1, matrix[m - 1][n - 1] + penalty)
            }
        }

        return matrix[cmpLength][length]
    }
}

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