from typing import Dict


def pattern_edit_distance(
    s: str, pattern: str, stands_for: Dict[str, str]) -> int:
  """The minimum number of edits required to make s match the pattern.

  An edit is the addition, deletion, or replacement of a character.

  Characters in the pattern are treated as literals, unless they appear in as
  keys in the the stands_for dictionary, in which case they "stand for" any one
  of the values in stands_for[char].

  If stands_for is empty, then this is the Levenshtein distance between s and
  the pattern.

  Args:
    stands_for: A dictinary from character to collection of characters (a
      string). When comparing the entity's text to the given pattern, anytime a
      key in this dictionary appears in the pattern, any of the characters in
      the corresponding dictionary value will be considered a pattern match.

  Example:
    pattern_edit_distance("abc123", "aaazzz", {"z": "23"}) is 3. The "b" and "c"
    need to be changed to "a", and the "1" needs to be changed to a "2" or a "3".
  """

  if not s:
    return len(pattern)
  if not pattern:
    return len(s)

  M = [[0 for _ in range(len(pattern) + 1)] for _ in range(len(s) + 1)]
  # M[i][j] is the pattern edit distance between s[:i] and pattern[:j].
  for i in range(len(s) + 1):
    M[i][0] = i
  for j in range(len(pattern) + 1):
    M[0][j] = j

  for i in range(1, len(s) + 1):
    for j in range(1, len(pattern) + 1):
      if pattern[j - 1] in stands_for:
        cost = 0 if s[i - 1] in stands_for[pattern[j - 1]] else 1
      else:
        cost = 0 if s[i - 1] == pattern[j - 1] else 1
      M[i][j] = min(
          [
              1 + M[i - 1][j],
              1 + M[i][j - 1],
              cost + M[i - 1][j - 1],
          ])

  return M[len(s)][len(pattern)]