Pretty inefficient computation of minimum edit distance between two strings

edit_distance.py

# Generate all substrings of string recursively
def substrings(string):
  #base case
  if len(string) == 0: return ''
  else:
    ret = [string]
    #Slide from left
    for x in range(0, len(string)):
      sub = string[x:-1]
      ret.append(sub)
      subs = substrings(sub)
      for substr in subs:
        if substr != '' and substr not in ret: ret.append(substr)

    #Slide from right
    for x in range(1, len(string)-1):
      ret.append(string[0:-x])
      sub = string[x:]
      ret.append(sub)
      subs = substrings(sub)
      for substr in subs:
        if substr != '' and substr not in ret: ret.append(substr)

    return ret

def edit_distance(n1, n2):
  minD = len(n2)
  minSub = ''
  for sub in substrings(n1):
    if sub in n2:
      dist = abs(len(n2) - len(sub))
      if dist <= minD:
        minD = dist
        minSub = sub
  if minSub != '': return minD
  else: return len(n2) + abs(len(n2)-len(n1))

test_cases = [
  {'n1': 'rob', 'n2': 'bob', 'dist': 1},
  {'n1': 'abcdxyz', 'n2': 'bbcdxywa', 'dist': 3},
  {'n1': 'randy', 'n2': 'robert', 'dist': 5},
  {'n1': 'randy', 'n2': 'conrados', 'dist': 6},
  {'n1': 'randy', 'n2': 'josh', 'dist': 5}
]

for test in test_cases:
  n1 = test['n1']
  n2 = test['n2']
  assert(edit_distance(n1, n2) == test['dist'])
  print('Count of character edits to convert ' + n1 + ' to ' + n2 + ' is ' + str(edit_distance(n1, n2)))