// TypeScript
function minDistance1 = (word1: string, word2: string): number => {
  const m = word1.length;
  const n = word2.length;

  const distances: number[][]= new Array(m + 1)
    .fill(0)
    .map(_ => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    distances[i][0] = i;
  }

  for (let j = 1; j <= n; j++) {
    distances[0][j] = j;
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i-1] === word2[j-1]) {
        distances[i][j] = distances[i-1][j-1];
      }
      else {
        distances[i][j] = 1 + Math.min(
          distances[i-1][j],
          distances[i][j-1],
          distances[i-1][j-1]
        );
      }
    }
  }

  return distances[m][n];
};

const minDistance2 = (word1: string, word2: string): number => {
  const m = word1.length;
  const n = word2.length;

  // always make word1 the shorter one to minimize space
  if (m > n) {
    return minDistance2(word2, word1);
  }

  let prev: number[] = new Array(m + 1).fill(0).map((_, i) => i);
  let curr: number[] = new Array(m + 1).fill(0);

  for (let j = 1; j <= n; j++) {
    curr[0] = j;
    for (let i = 1; i <= m; i++) {
      if (word1[i-1] === word2[j-1]) {
        curr[i] = prev[i-1];
      }
      else {
        curr[i] = 1 + Math.min(
          prev[i-1],
          curr[i-1],
          prev[i]
        );
      }
    }

    [prev, curr] = [curr, prev];
  }

  return prev[m];
}

-- Haskell
import Data.Array (array, (!))
minDistance1 :: String -> String -> Int
minDistance1 word1 word2 = dp ! (m, n)
  where
    m = length word1
    n = length word2
    -- to create a 2D array with indices from (0, 0) to (m, n)
    dp = array ((0, 0), (m, n))
         [((i, j), calc i j) | i <- [0..m], j <- [0..n]]
    calc 0 j = j
    calc i 0 = i
    calc i j
      | word1 !! (i - 1) == word2 !! (j - 1)
        = dp ! (i - 1, j - 1)
      | otherwise
        = 1 + minimum [ dp ! (i - 1, j - 1)
                      , dp ! (i,     j - 1)
                      , dp ! (i - 1, j)
                      ]


minDistance2 :: String -> String -> Int
minDistance2 word1 word2 = (dp !! m) !! n
  where
    m = length word1
    n = length word2
    dp = [
           [ calc i j
           | j <- [0..n]
           ]
         | i <- [0..m]
         ]
    calc :: Int -> Int -> Int
    calc 0 j = j
    calc i 0 = i
    calc i j
      | word1 !! (i - 1) == word2 !! (j - 1)
      = (dp !! (i - 1)) !! (j - 1)
      | otherwise
      = 1 + minimum [ (dp !! (i - 1)) !! (j - 1)
                    , (dp !! (i))     !! (j - 1)
                    , (dp !! (i - 1)) !! (j)
                    ]

;; chez scheme
(import (chezscheme))

(define (min-distance word1 word2)
  (let* ((m (string-length word1))
          (n (string-length word2))
          ;; 2D vector (m + 1) x (n + 1)
          (dp (make-vector (+ m 1))))

    (do ((i 0 (+ i 1)))
        ((> i m))
      (vector-set! dp i (make-vector (+ n 1))))

    (do ((i 1 (+ i 1)))
        ((> i m))
      (vector-set! (vector-ref dp i) 0 i))

    (do ((j 1 (+ j 1)))
        ((> j n))
      (vector-set! (vector-ref dp 0) j j))

    (do ((i 1 (+ i 1)))
        ((> i m))
      (do ((j 1 (+ j 1)))
          ((> j n))
        (if (char=? (string-ref word1 (- i 1)) (string-ref word2 (- j 1)))
          (vector-set! (vector-ref dp i) j (vector-ref (vector-ref dp (- i 1)) (- j 1)))
          (vector-set! (vector-ref dp i) j (+ 1 (min (vector-ref (vector-ref dp (- i 1)) (- j 1))
                                                     (vector-ref (vector-ref dp (- i 1))       j)
                                                     (vector-ref (vector-ref dp i)       (- j 1))))))))

    (vector-ref (vector-ref dp m) n)))