Skip to content

Instantly share code, notes, and snippets.

Created June 27, 2014 05:54
Show Gist options
  • Save bgreenlee/52d93a1d8fa1b8c1f38b to your computer and use it in GitHub Desktop.
Save bgreenlee/52d93a1d8fa1b8c1f38b to your computer and use it in GitHub Desktop.
Levenshtein Distance in Swift
* Levenshtein edit distance calculator
* Usage: levenstein <string> <string>
* To compile:
* sudo xcode-select -switch /Applications/
* xcrun swift -sdk $(xcrun --show-sdk-path --sdk macosx) levenshtein.swift
import Foundation
// return minimum value in a list of Ints
func min(numbers: Int...) -> Int {
return numbers.reduce(numbers[0], {$0 < $1 ? $0 : $1})
func levenshtein(aStr: String, bStr: String) -> Int {
// create character arrays
let a = Array(aStr)
let b = Array(bStr)
// initialize matrix of size |a|+1 * |b|+1 to zero
var dist = Int[][]()
for row in 0...a.count {
dist.append(Int[](count: b.count + 1, repeatedValue: 0))
// 'a' prefixes can be transformed into empty string by deleting every char
for i in 1...a.count {
dist[i][0] = i
// 'b' prefixes can be created from empty string by inserting every char
for j in 1...b.count {
dist[0][j] = j
for i in 1...a.count {
for j in 1...b.count {
if a[i-1] == b[j-1] {
dist[i][j] = dist[i-1][j-1] // noop
} else {
dist[i][j] = min(
dist[i-1][j] + 1, // deletion
dist[i][j-1] + 1, // insertion
dist[i-1][j-1] + 1 // substitution
return dist[a.count][b.count]
if Process.arguments.count != 3 {
println("Usage: levenstein <string> <string>")
println(levenshtein(Process.arguments[1], Process.arguments[2]))
Copy link

Smotrov commented Nov 18, 2014

Dramatically slower then this implementation
I've send couple of hours to make it faster but... It seems like Swift arrays and Strings manipulation are not as fast as objC.

On 2000 random Strings calculations Swift implementation is about 100(!!!) times slower then ObjC.

Copy link

You'll find an improved version here :

Copy link

shergin commented Jan 8, 2016

Here is my (more generalized) version:

Copy link

I went and improved on the prior versions to incorporate all of the optimizations available in Swift 2.2. You can find the gist here:

However, I've also turned it into a cocoapod:

Copy link

joe528 commented Sep 22, 2016

Statements like this for i in 1...a.count will lead to crash if a.count is 0.

Always use something like 1..<count to avoid any possibility of crashing.

Copy link

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment