def _ComputeEditDistance(hs, rs):
  """Compute edit distance between two list of strings.

  Args:
    hs: the list of words in the hypothesis sentence
    rs: the list of words in the reference sentence

  Returns:
    edit distance as an integer
  """
  dr, dh = len(rs) + 1, len(hs) + 1
  dists = [[]] * dr

  # initialization for dynamic programming
  for i in range(dr):
    dists[i] = [0] * dh
    for j in range(dh):
      if i == 0:
        dists[0][j] = j
      elif j == 0:
        dists[i][0] = i

  # do dynamic programming
  for i in range(1, dr):
    for j in range(1, dh):
      if rs[i - 1] == hs[j - 1]:
        dists[i][j] = dists[i - 1][j - 1]
      else:
        tmp0 = dists[i - 1][j - 1] + 1
        tmp1 = dists[i][j - 1] + 1
        tmp2 = dists[i - 1][j] + 1
        dists[i][j] = min(tmp0, tmp1, tmp2)

  return dists[-1][-1]