@udacity

gistfile1.py

#Spelling Correction

#Double Gold Star

#For this question, your goal is to build a step towards a spelling corrector,
#similarly to the way Google used to respond,

#    "Did you mean: audacity"


#when you searched for "udacity" (but now considers "udacity" a real word!).

#One way to do spelling correction is to measure the edit distance between the
#entered word and other words in the dictionary.  Edit distance is a measure of
#the number of edits required to transform one word into another word.  An edit
#is either: (a) replacing one letter with a different letter, (b) removing a
#letter, or (c) inserting a letter.  The edit distance between two strings s and
#t, is the minimum number of edits needed to transform s into t.

#Define a procedure, edit_distance(s, t), that takes two strings as its inputs,
#and returns a number giving the edit distance between those strings.

#Note: it is okay if your edit_distance procedure is very expensive, and does
#not work on strings longer than the ones shown here.

#The built-in python function min() returns the mininum of all its arguments.

#print min(1,2,3)
#>>> 1

def calc(lst):
    if isinstance(lst, list):
        if len(lst) > 2: 
            a,b,c=lst
            return min(calc(a), calc(b), calc(c))
        h,t = lst
        return calc(h) + t
    return lst

def process(s,t):
    if not(s and t):  
        if s or t:
            return len(s) if s else len(t)  # either s or t is present, get it's length
        return 0  # s & t are empty so no change
    
    return [
                   [process(s[:-1], t[:-1]), 0 if s[-1] == t[-1] else 1],
                   [process(s, t[:-1]), 1],
                   [process(s[:-1], t), 1]
    ]

def edit_distance(s,t):
    x = process(s,t)
    return min( calc(x[0]), calc(x[1]), calc(x[2]) )