I tried to write a recursive implementation for edit_distance, but kept getting errors, so I ended up submitting a non-recursive solution. At least, I think it's a solution, inasmuch as it was labeled "Correct" when I resubmitted it after the deadline. (I had a stupid typo in my recursive implementation that I finally caught -- but only after the submission deadline.)

Anyway, my code for the non-recursive is below. I used a dictionary to keep track of all the distances as I went through the strings.

What has me confused is that, at the end, if I print out my entire dictionary (as opposed to returning the one final result), all of my keys are two-value pairs enclosed in parentheses -- such as: (2,1) or (0,3). I expected the keys to be lists of two values. But a list would be enclosed in square brackets. We didn't see anything in this course that looked like those pairs in parentheses.

But, I submitted this since it worked -- and the function wasn't returning anything other than the dictionary value, so the keys didn't show up anyway.

My question is: What on earth did I do? Are these pairs the expected output of dictionary assignments that I did this way? Or is it the merest coincidence that this works at all? (I tested it with the long list of edit_distance test strings that was posted in another comment, and they all worked.)

Of course, if I'd caught that stupid typo earlier, none of this would be an issue for me!

Thanks in advance to anyone who can offer some insight.

def edit_distance(s,t):

     counter = {}

     for i in range(0,(len(s)+1)):

         counter[i,0] = i

     for j in range(0,(len(t)+1)):

         counter[0,j] = j

     for i in range(len(s)):

         for j in range(len(t)):

             if t[j] == s[i]:

                 counter[i+1,j+1] = counter[i,j]

             else:

                 counter[i+1,j+1] = 1 + min(counter[i,j],counter[i,j+1],counter[i+1,j])

     return counter[len(s),len(t)]