lev.swift

func lev(s: String, t: String) -> Int {
  if s == t { return 0 }
  let sLen = s.characters.count
  let tLen = t.characters.count

  if sLen == 0 { return tLen }
  if tLen == 0 { return sLen }

  var d: [[Int]] = []

  for _ in 0...sLen { d.append([Int](repeating: 0, count: tLen + 1)) }

  for i in 0...sLen { d[i][0] = i }

  for j in 0...tLen { d[0][j] = j }

  for j in 1...tLen {
    for i in 1...sLen {
      if s[s.index(s.startIndex, offsetBy: i - 1)] == t[t.index(t.startIndex, offsetBy: j - 1)] {
        d[i][j] = d[i - 1][j - 1]
      } else {
        let deletions = d[i - 1][j] + 1
        let insertions = d[i][j - 1] + 1
        let substitutions = d[i - 1][j - 1] + 1
        d[i][j] = min(deletions, insertions, substitutions)
      }
    }
  }

  return d[sLen][tLen]
}

func lev2(s: String, t: String) -> Int {
  if s == t { return 0 }

  let sLen = s.characters.count
  let tLen = t.characters.count

  if sLen == 0 { return tLen }
  if tLen == 0 { return sLen }

  var v0 = [Int](repeating: 0, count: tLen + 1)
  var v1 = [Int](repeating: 0, count: tLen + 1)

  for i in 0..<v0.count { v0[i] = i }

  for i in 0..<sLen {
    v1[0] = i + 1
      for j in 0..<tLen {
        var cost = 1
        if s[s.index(s.startIndex, offsetBy: i)] == t[t.index(t.startIndex, offsetBy: j)] {
          cost = 0
        }
        v1[j + 1] = min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost)
      }
      for j in 0..<v0.count { v0[j] = v1[j] }
    }

    return v1[tLen]
}

print(lev(s: "book", t: "back"))
print(lev2(s: "book", t: "back"))
print(lev(s: "kitten", t: "sitting"))
print(lev2(s: "kitten", t: "sitting"))