Skip to content

Latest commit

 

History

History
10 lines (9 loc) · 457 Bytes

File metadata and controls

10 lines (9 loc) · 457 Bytes

Idea

This problem is a modification of 72. Edit Distance. The idea is very similar, suppose that we have a function f(x, y) which could return the minimum distance for word x and y. Then we can have this recursive formula:

if x[-1] != y[-1]:
	f(x, y) = min( f(x[:-1], y)+ord(x[-1]), f(x, y[:-1])+ord(y[-1]) ) 
	#delete x[-1], delete y[-1]
else:
	f(x, y) = f(x[:-1], y[:-1])