Levenshtein distance in Swift3

user_3758523 0
Viewed 1801

I'm using a tutorial from Rosetta Code to calculate Levenshtein distance. It seems their code is in Swift2 so I get this error Binary operator '+' cannot be applied to operands of type '[Int]' and 'Repeated<String.CharacterView>' when doing this: var cur = [i + 2] + empty where let empty = repeatElement(s, count: 0). How can I go about this?

rosetta-code swift3 levenshtein-distance swift
4 Answers
func ~=(string: String, otherString: String) -> Bool {
    return string.levenshteinDistanceScore(to: otherString) >= 0.85 
}
user_99914970

Since @Daniel Illescas answer is not working, here is working version with Int return type and with assert.

extension String {

    func levenshteinDistance(to string: String, ignoreCase: Bool = true, trimWhiteSpacesAndNewLines: Bool = true) -> Int {
        
        var firstString = self
        var secondString = string
        
        if ignoreCase {
            firstString = firstString.lowercased()
            secondString = secondString.lowercased()
        }
        
        if trimWhiteSpacesAndNewLines {
            firstString = firstString.trimmingCharacters(in: .whitespacesAndNewlines)
            secondString = secondString.trimmingCharacters(in: .whitespacesAndNewlines)
        }
        
        let empty = [Int](repeating: 0, count: secondString.count)
        var last = [Int](0...secondString.count)
        
        for (i, tLett) in firstString.enumerated() {
            var cur = [i + 1] + empty
            for (j, sLett) in secondString.enumerated() {
                cur[j + 1] = tLett == sLett ? last[j] : Swift.min(last[j], last[j + 1], cur[j]) + 1
            }
            
            last = cur
        }
        
        if let validDistance = last.last {
            return validDistance
        }
        
        assertionFailure()
        return 0
    }
}
user_65709140
Related