Mininum Number of Edits

minEdits.swift

func minEdit(_ s1: String, _ s2: String) -> Int {
    
  if s1.isEmpty {
    return s2.count
  }
  if s1.first == s2.first {
    return minEdit(String(s1.suffix(s1.count-1)), String(s2.suffix(s2.count-1)))
  } else if s1.count == s2.count {
    return 1 + minEdit(String(s1.suffix(s1.count-1)), String(s2.suffix(s2.count-1)))
  } else {
    let replacement: Int = 1 + minEdit(String(s1.suffix(s1.count-1)), String(s2.suffix(s2.count-1)))
    let insertion: Int = 1 + minEdit(s1, String(s2.suffix(s2.count-1)))
    return min(replacement, insertion)
  }
}

func minEditMemo(_ s1: String, _ s2: String) -> Int {
  
  var memo: [[Int]] = Array(repeating: Array(repeating: -1, count: s2.count + 1), count: s2.count + 1)
  return minEditHelper(s1, s2, i: 0, j: 0, memo: &memo)
}


func minEditHelper(_ s1: String, _ s2: String, i: Int, j: Int, memo: inout [[Int]]) -> Int {
  if s1.isEmpty {
    return s2.count
  }
  
  if memo[i][j] != -1 { return memo[i][j] }
  
  if s1.first == s2.first {
    let next: Int = minEditHelper(String(s1.suffix(s1.count-1)), String(s2.suffix(s2.count-1)), i:i+1,j:j+1, memo: &memo)
    memo[i][j] = next
    return memo[i][j]
  } else if s1.count == s2.count {
    let replacement = 1 + minEditHelper(String(s1.suffix(s1.count-1)), String(s2.suffix(s2.count-1)), i:i+1, j: j+1, memo: &memo)
    memo[i][j] = replacement
    return memo[i][j]
  } else {
    let replacement: Int = 1 + minEditHelper(String(s1.suffix(s1.count-1)), String(s2.suffix(s2.count-1)), i: i+1, j: j+1, memo: &memo)
    let insertion: Int = 1 + minEditHelper(s1, String(s2.suffix(s2.count-1)), i: i, j: j+1, memo: &memo)
    memo[i][j] = min(replacement, insertion)
    return memo[i][j]
  }
}

print(minEditMemo("barns", "barthom"))