فاصله Levenshtein حداقل تعداد عملیات‌های ممکن (insertion، deletion و substitution) برای تبدیل یه رشته به یه رشته دیگه رو اندازه‌گیری می‌کنه. از کاربردهاش هم میشه به spell-checking و autocorrect و همینطور پیدا کردن اسم‌ها یا عبارت‌های مشابه بخصوص توی سرچ اشاره کرد.

این مثال رو در نظر بگیرید. فاصله بین kitten و sitting سه هستش:
kitten -> sitten -> sittin -> sitting

برای محاسبه‌ش از dynamic programming استفاده می‌کنیم. grid پرشده مثال این شکلی میشه (1). مقدار هر سلول طبق فرمول (2) بدست اومده و عدد داخلش نشون میده حداقل فاصله ویرایشی بین دو prefix متناظر با اون سلول چقدره. مثلا سلول (3,2) مقدار 2 داره؛ این یعنی فاصله بین si و kit دو هستش. مقدار سلول پایین-راست هم جواب نهایی‌مونه.

برای تمرینش می‌تونین مسئله لیتکد 72. Edit Distance رو حل کنین.

#algorithm

@techstuff100