def ComputeEditDistanceMatrix(hyp_words, ref_words):
  """Compute edit distance between two list of strings.

  Args:
    hyp_words: the list of words in the hypothesis sentence
    ref_words: the list of words in the reference sentence

  Returns:
    Edit distance matrix (in the format of list of lists), where the first
    index is the reference and the second index is the hypothesis.
  """
  reference_length_plus = len(ref_words) + 1
  hypothesis_length_plus = len(hyp_words) + 1
  edit_dist_mat = [[]] * reference_length_plus

  # Initialization.
  for i in range(reference_length_plus):
    edit_dist_mat[i] = [0] * hypothesis_length_plus
    for j in range(hypothesis_length_plus):
      if i == 0:
        edit_dist_mat[0][j] = j
      elif j == 0:
        edit_dist_mat[i][0] = i

  # Do dynamic programming.
  for i in range(1, reference_length_plus):
    for j in range(1, hypothesis_length_plus):
      if ref_words[i - 1] == hyp_words[j - 1]:
        edit_dist_mat[i][j] = edit_dist_mat[i - 1][j - 1]
      else:
        tmp0 = edit_dist_mat[i - 1][j - 1] + 1
        tmp1 = edit_dist_mat[i][j - 1] + 1
        tmp2 = edit_dist_mat[i - 1][j] + 1
        edit_dist_mat[i][j] = min(tmp0, tmp1, tmp2)

  return edit_dist_mat