gistfile1.py

#!/usr/bin/python
# -*- coding: utf-8 -*-
import os
import platform
import random

print "Content-Type: text/html"

rec_cnt = 0
ed_cache = {}

def edit_dist_cache(a, b):
    cache_key = a + ',' + b
    if cache_key in ed_cache:
        return ed_cache[cache_key]
    ret = edit_dist(a, b)
    ed_cache[cache_key] = ret
    return ret
    
def edit_dist(a, b):
    global rec_cnt
    # base case len(a) == 0 or len(b) == 0
    rec_cnt += 1
    if len(a) == 0:
        return len(b)
    if len(b) == 0:
        return len(a)
        
    # 2. first characters are equal
    if a[0] == b[0]:
        return edit_dist_cache(a[1:], b[1:])
    # 3. we have to find minimum 1 + deletion, 1 + substitution, 1 + insertion (deletions includes insertion)
    # ex.:
    # dacity
    # acity
    return 1 + min(edit_dist_cache(a[1:], b), edit_dist_cache(a, b[1:]), edit_dist_cache(a[1:], b[1:]))

print edit_dist_cache('smothered', 'the'), rec_cnt, ed_cache
exit()
t=[
            ['audacity',        'udacity',      1],
            ['audacity',        'Udacity',      2],
            ['peter',           'sarah',        5],
            ['pete',            'peter',        1],
            ['udc',             'audacity',     5],
            ['audacity',        'udc',          5],
            ['audacity',        'udacious',     4],
            ['python',          'pytohn',       2],
            ['udacity',         'university',   6],
            ['university',      'udacity',      6],
            ['edata',           'database',     5],
            ['smothered',       'moth',         5],
            ['moth',            'smothered',    5],
            ['smothered',       'other',        4],
            ['other',           'smothered',    4],
            ['the',             'smothered',    6],
            ['smothered',       'the',          6],
            ['there',           'smothered',    4],
            ['smothered',       'there',        4],
            ['horror',          'mirror',       2],
            ['beehive',         'behave',       2],
            ['audacity',        'xurdrity',     4]
            #['A man, a plan, a canal - Panama!', 'Doc, note: I dissent. A fast never prevents a fatness. I diet on cod.', 54]#,
            #,['amanaplanacanalpanama', 'docnoteidissentafastneverpreventsafatnessidietoncod', 42]#,
            #['klebsiella pneumonia', 'salivating puma', 15]
        ]
for y in t:
    rec_cnt = 0
    print "edit_dist('",y[0],"','",y[1],"') = ",edit_dist(y[0],y[1]), rec_cnt, y[2]