Snippet to find edit distance in Bash

edit_distance.sh

#!/bin/bash

function get_coord_index() {
  local array_width=$1
  local i=$2
  local j=$3

  echo "$(((i * $array_width) + j))"
}

function get_edit_distance() {
  local string1="${1}"
  local string2="${2}"
  local array_width=$((${#string2} + 1))

  declare -i current_index
  declare -i index_to_be_copied_from
  declare -a memo

  # initialize array with zeros
  for ((i = 0; i < $(((${#string1} + 1) * (${#string2} + 1))); i++)); do
    memo[i]=0
  done

  for ((i = 0; i < ${#string1}; i++)); do
    current_index=$(get_coord_index ${array_width} $((i + 1)) 0)
    (( memo[${current_index}] = i + 1 ))
  done

  for ((j = 0; j < ${#string2}; j++)); do
    current_index=$(get_coord_index ${array_width} 0 $((j + 1)))
    (( memo[${current_index}] = j + 1 ))
  done

  for ((i = 0; i < ${#string1}; i++)); do
    for ((j = 0; j < ${#string2}; j++)); do
      current_index=$(get_coord_index ${array_width} $((i + 1)) $((j + 1)))

      if [[ "${string1:$i:1}" == "${string2:$j:1}" ]]; then
        index_to_be_copied_from=$(get_coord_index ${array_width} $i $j)
        memo[$current_index]=${memo[$index_to_be_copied_from]}
      else
        local index_to_be_compared=(
          $(get_coord_index ${array_width} $((i + 1)) $j)
          $(get_coord_index ${array_width} $i $((j + 1)))
          $(get_coord_index ${array_width} $i $j)
        )

        memo[$current_index]=${memo[${index_to_be_compared[0]}]}
        for k in "${index_to_be_compared[@]}"; do
          [ ${memo[k]} -le ${memo[$current_index]} ] && memo[$current_index]=${memo[k]}
        done
        (( memo[$current_index]++ ))
      fi
    done
  done

  echo ${memo[$(get_coord_index ${array_width} ${#string1} ${#string2})]}
}