<s> from string import ascii_letters <EOL> class Trie_Node : <EOL> def __init__ ( self ) : <EOL> self . isWord = False <EOL> self . s = { c : None for c in ascii_letters } <EOL> def add ( T , w , i = <NUM_LIT:0> ) : <EOL> """<STR_LIT>""" <EOL> if T is None : <EOL> T = Trie_Node ( ) <EOL> if i == len ( w ) : <EOL> T . isWord = True <EOL> else : <EOL> T . s [ w [ i ] ] = add ( T . s [ w [ i ] ] , w , i + <NUM_LIT:1> ) <EOL> return T <EOL> def Trie ( S ) : <EOL> """<STR_LIT>""" <EOL> T = None <EOL> for w in S : <EOL> T = add ( T , w ) <EOL> return T <EOL> def spell_check ( T , w ) : <EOL> """<STR_LIT>""" <EOL> assert T is not None <EOL> dist = <NUM_LIT:0> <EOL> while True : <EOL> u = search ( T , dist , w ) <EOL> if u is not None : <EOL> return u <EOL> dist += <NUM_LIT:1> <EOL> def search ( T , dist , w , i = <NUM_LIT:0> ) : <EOL> """<STR_LIT>""" <EOL> if i == len ( w ) : <EOL> if T is not None and T . isWord and dist == <NUM_LIT:0> : <EOL> return "<STR_LIT>" <EOL> else : <EOL> return None <EOL> if T is None : <EOL> return None <EOL> f = search ( T . s [ w [ i ] ] , dist , w , i + <NUM_LIT:1> ) <EOL> if f is not None : <EOL> return w [ i ] + f <EOL> if dist == <NUM_LIT:0> : <EOL> return None <EOL> for c in ascii_letters : <EOL> f = search ( T . s [ c ] , dist - <NUM_LIT:1> , w , i ) <EOL> if f is not None : <EOL> return c + f <EOL> f = search ( T . s [ c ] , dist - <NUM_LIT:1> , w , i + <NUM_LIT:1> ) <EOL> if f is not None : <EOL> return c + f <EOL> return search ( T , dist - <NUM_LIT:1> , w , i + <NUM_LIT:1> ) </s>
